Question

True or False? If true, then explain why (try to prove it!). If false, then provide a counterexample (an instance in which the claim is false).

(a) For any connected graph G, all internal nodes of the BFS tree on G have the same number of children.

(b) For any connected graph G, the DFS tree on G and the BFS tree on G have the same number of edges.

(c) Consider a graph G. If B is a leaf in a DFS tree rooted at node A, then it must also be a leaf in a BFS tree rooted at node A.

Answer 1

Solution

(a) False, for any connected graph G , all internal nodes of the BFS tree on G have the same number of children. If BFS on K (3 ,3) , one internal node (the root) has 3 children, and the other internal node has only 2 children.

(b) True: Suppose the input graph is an undirected tree T. Both DFS and BFS must produce a tree, so they must contain all the edges of T (all trees have. V− 1 edges). Since two trees must be identical if they have the same root and same edges, both DFS and BFS will produce T.

(c) True, If B is a leaf in a DFS tree rooted at node A, then it must also be a leaf in a BFS tree rooted at node A.