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

Let us assume that T_B = T_D = T but there is an edge e belonging to G which is not in T. This is only possible if the vertex on the other side is visited in bothe BFS and DFS traversal. However, if there is a DFS back edge, then BFS must have used it, which is a contradiction.

Hence if T_B = T_D every edge of G is included and hence, G is a tree.