hw5.dvi

Problem 1: True or False? If true, give a short proof. If false, give a counterexample: (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.