1
$\begingroup$

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.

$\endgroup$

closed as unclear what you're asking by Raphael Jan 31 at 7:20

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ This question appears to be unsuited for this site because questions of the form: "This is the exercise problem, this is my solution. Please grade!" are not interesting for anyone but you. Please see this related meta discussion, and these hints on asking questions about exercise problems. If you want to ask a specific question about a specific part of your attempt, please edit the question accordingly and it may be reopened. Otherwise, you might want to visit Computer Science Chat and get some feedback there. $\endgroup$ – Raphael Jan 31 at 7:19