Prove that if a DFS and BFS trees in graph G are the same than

ok here we go...

Proof:

If the some graph G has the same DFS and BFS then that means that G should not have any cycle(work out for any G with a cycle u will never get the same BFS and DFS .... and for a graph without any cycle u will get the same BFS/DFS).

We will prove it by contradiction:
So say if T is the tree obtained by BFS/DFS, and let us assume that G has atleast one edge more than T. So one more edge to T(T is a tree) would result in a cycle in G, but according to the above established principle no graph which has a cycle would result the same DFS and BFS, so out assumption is a contradiction.

Hence G should have more edges than T, which implies that if the BFS and DFS for a graph G are the same then the G = T.

Hope this helps u......................