Proving a connected graph is a tree if the DFS and BFS traversals from the same node are equivalent Let $G$ be a connected graph and $v$ be a vertex in $G$. Suppose a DFS traversal from $u$ is performed resulting in a tree $T$, and a BFS from $u$ also results in the same tree $T$. I would like to show that $T = G$.
My main problem for this is that I am not sure how to initially approach this proof, and given my current approach is within reason I am stuck as for my next step. 
My current thought is to go by contradiction and suppose that $T$ is both the DFS and BFS tree of $G$ with $u$ being the root, but $T \neq G$. As $T \subset G$, there must exist an edge $e \in G$ such that $e \notin T$ (since $G$ is connected it cannot be the case that there is a vertex in $G$ that is not in $T$). From here I believe my contradiction will come from the DFS and BFS traversals not being equivalent, but this is where I am stuck in this approach. 
Could anyone hint at my next step or give me an idea for another approach to the proof?
 A: Hint:


*

*It is not true for directed graphs, that is, there exists a directed graph $G$ and a DFS run and a BFS run such that both trees are the same, but $G$ is not a tree. An example might be a back-edge.

*In the case of undirected graphs it still might not be true, e.g. if the graph is non-simple, i.e. it allows more than one edges between two vertices.

*It is true, if the graph is simple, connected and undirected, and the very basic observation is that $G$ is a tree if and only if every edge was traversed in the BFS/DFS search.

*Suppose that $T_{BFS} = T = T_{DFS}$, but that there is $e \in E(G) \setminus E(T)$, that is, an edge that was not visited by any of the algorithms. The only reason the edge was not traversed could be that the vertex on the other side was already visited, but if there is a DFS-back-edge then BFS must have used it before.


I hope this helps $\ddot\smile$
A: Note that it is essential that the trees are rooted trees.
If you start with a paw (a triangle with an attached edge, so this certainly is not a tree) the BFS-tree from the vertex with degree 1 is a claw
and the DFS-tree from a vertex with degree 2 is also a claw for one of the choices of the second vertex.
This suggests that your proof must involve the root somehow.
If $G$ and $T$ are not equal, then $G$ must contain a cycle.
Let $v$ be a vertex that is on a cycle and has minimum distance to the root $u$ ($v$ and $u$ may be equal).
Let $v=v_1,\ldots,v_n,v$ be an actual cycle through $v$.
Prove, using the BFS description that both $vv_2$ and $vv_n$ must be edges of $T$.
Prove, using the DFS description that $vv_2$ can $vv_n$ cannot possibly be both edges of $T$.
