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

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

Solution

BFS starts by visiting the root.It then visits the vertices which are at a distance of 1 edge from root. Say there are 4 vertices a,b,c,d adjacent to root.Then bfs will visit these 4 vertices just after visiting root.Once bfs is done visiting vertices at a distance of 1 edge from root. It then takes the first vertex visited after root and repeats the same procedure.Which vertex was the first one, this is handled by queue data structureDFS starts by visiting the root. It will not visit all vertices adjacent to root after visiting root, but will go into the depth of graph. Once it visits root, it visits only vertex adjacent to root and then will start dfs from that vertex itself, that is it goes into depth before visiting all vertices adjacent to root. It will only come to them once it has visited the vertices in depth of direction in which it started the dfsAny other tree different from above two trees will be like where an intermediate vertex v exists at level x and it has more than 1 children(say 2) c1 and c2 at level x+1, What bfs will do is visit v and then c1 and c2, but what dfs will do is visit v and then c1 and then child of c1 so clearly the traversals wont be the same in these two cases.