Let G be a connected, undirected graph containing some vertex s. let's say that BFS and DFS are both run on G starting at s and that the breadth first search and depth first search trees produced are the same. Show that G is a tree.
Would this be good enough?
In order to show that G is a tree Let us denote the tree produced by BFS and DFS be T. Assume that G is not a tree, which means there must be an edge (u, v) ∈ G and such that (u, v) $\not\in $ T. ( G has more edges than T)
In such case, as the DFS tree forming, there will be a backedge. That implies there is a cycle in G . That is because if v is discovered first by DFS, DFS must also find V later before finishing explore v.
On the other hand, as the BFS tree forming, u and v can only differ by one level, which means there is not cycle.
With the fact that BFS and DFS tree are the same tree, it implies that one of u and v is an ancestor of the other and they can only differ by one level. Therefore, all edges connecting T are the same as connecting G and G is a tree.