Consider a rooted connected graph G V E and a vertex u V Le

Consider a rooted, connected graph G = (V, E), and a vertex u V. Let T_B be a BFS tree of G rooted at u, and let T_D be a DFS tree of G rooted at u. Prove that if T_B = T_D, then G is a tree.

Solution

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 (ie |V | 1 edges). Since TB =TD must be identical if they have the same root and same edges, both DFS and BFS will produce T.

Conversely, suppose the input graph G is undirected and connected but is not a tree. Then G must contain a cycle C. let C have k nodes v1, v2, . . . , vk, i.e. C is the cycle v1 v2 . . . vk v1. Now in the DFS tree, nodes v1, v2, . . . , vk will all be on the same path from the root to a leaf. Since the all vi are all strongly connected, DFS traversal from a starting node will visit the remaining at some point during the explore of starting node.

However, in BFS tree, nodes v1, v2, . . . , vk will form at least two branches (since bfs is performing on a cycle) braching from the node first visited.

Therefore,if T_B = TD then G is a Tree.