Please tell me if my proof is correct or not
We have a connected graph, and specific vertex u in V(G).
Suppose we compute the dfs tree of G rooted at u and obtain tree T.
Now imagine we compute the bfs tree of G rooted at u and we obtain the same tree T.
Prove that the only way this is possible is if G=T
Proof by contradiction.
Assume that dfs tree and bfs tree are equal to T, but G is not equal to T.
This implies that G contains at least one edge not in T.
We also know that any such edges are part of a cycle, otherwise they would have been in T.
So there is at least one Cycle C= p1, p2, p3, p_{k} with p_{k} = p1, consisting of distinct nodes k>= 3, in G.
Assume that dfs and bfs algorithms will encounter the cycle at node p1.
Dfs will add the following edges to its tree (p1, p2), ...., (p_{k-2},(p_{k-1}) whereas bfs begins by adding edges (p1,p2), (p1,p_{k}) to its tree.
Already we see that dfs tree is not equal to bfs tree since bfs contains (p1,p_{k}) and dfs doesn’t contain this edge.
This contradicts our assumption that dfs and bfs have equal trees, and shows it must be the case that G=T.
The theorem only holds for undirected graphs (take any strongly connected circle digraph as a counterexample).
Back to undirected graphs, for an intuitive approach note that dfs maximizes the tree height while bfs minimizes it. That means on the first circle C hit, the subtrees covering C will differ.
Your proof formalizes the idea, so in general I'd say it's ok.
You didn't specify the dfs selection strategy, so there are 2 minor mistakes:
Instead of (p1,p2), then dfs may include (p1,p_{k}) or none of the edges at all ( ). Of course, dfs will never include both edges while bfs always will.
Dfs does not necessarily add k-1 circle edges to T. However, it will have visited all circle vertices before retracting to p1, thus all circle vertices will have been added to T at this time. Thus (p1,p_{k}) (dfs selection (p1,p2) on hitting p1 for the first time) or (p1,p2) ( else ), resp., will not be added.
You could formalize the latter by proving a small lemma:
Let (v, w) be an edge that dfs is adding in step n ( wlog assuming that the dfs moved from v to w ), T(n) be the partial dfs tree at step (n). Then all nodes from the connected component [w] in the subgraph G' induced by V(G) \ V(T(n)) will be added to the dfs tree before another edge (w, x) from E(G) will be added.