Given a connected and undirected graph $G=(V,E)$ and given $T_{BFS}$ the BFS tree that was called on $s\in V$ , also given $T_{DFS}$ that was called on the same vertex $s$. Show that $depth(T_{BFS})\leq depth(T_{DFS}$)
I will be happy to see some opinions on my solution.It will help me a lot.
My solution:
If $G$ is a tree then since $T_{BFS}$ has $|V|-1$ edges of $E$,
and $G$ has the same $|V|-1$ edges of $E$ we can conclude that $T_{BFS}=G$.
We can argue the same for $T_{DFS}$ and therefore $T_{BFS}=T_{DFS}$, and the cliam holds.
Second case – Proof (by contradiction):
If $G$ is connected and also $G$ is not a tree then it must contain a cycle on a path rooted at $s$.
Let $\{y,x\}$ be the $back\; edge$ on the cycle. let $z\in V$ be a third vertex on the cycle.The cycle is: $s\rightsquigarrow x\rightsquigarrow z\rightsquigarrow y\rightarrow x$ Now:
At $T_{DFS}$ we get : $d(s,y)\ge d(s,x)+2\;\;\;$ //at least 1 for $x\rightsquigarrow z $ and at least 1 for $z\rightsquigarrow y$
At $T_{BFS}$ we get: $d(s,y)=\delta(s,y)\leq \delta(s,x)+1 $ //triangle inequality for shortest path on an undirected and unweighted graph
To conclude , we have : $d(s,y)=\delta(s,y)\leq \delta(s,x)+1 < d(s,x)+2 \leq d(s,y)$ and we got a contradiction, since if the longest Path from $s$ to some $u$ do not contains a cycle than it contains in a tree (and we delt with it in case 1), otherwise the longest path contains a cycle, and in $T_{BFS}$ the path to the deepest edge in the cycle is shorter than the path to the deepest edge in the cycle if reached via $T_{DFS}$
Best Answer
Your proof seems to be getting at the right idea, but there are a few details missing that are important for a clear writeup. In order from most to least important:
You say that your second case is a proof by contradiction, but you never say what assumption you are making that leads to a contradiction.
The definition of the cycle and the "back edge" on it is under-specified. I assume from context that you're saying that there's specifically an edge $yx$ that's not part of $T_{DFS}$, from which we may conclude that $x$ lies somewhere on the path from $s$ to $y$ in $T_{DFS}$.
The notations $d(x,y)$ and $\delta(x,y)$ seem ambiguous given that there are three, not two, different distances between vertices to keep track of: the distance in $G$, the distance in $T_{DFS}$, and the distance in $T_{BFS}$. (You also have not said which of these are $d$ and which are $\delta$, but perhaps this has been decided for you if you're doing homework for a specific class.) As a result, your concluding inequality makes no sense.
Also, there is a much simpler argument: if $T_{BFS}$ has depth $d$, it is because there is a vertex $t$ at distance $d$ from $s$ (in $G$). This vertex cannot be at a depth smaller than $d$ in any other tree (any other spanning tree of $G$ rooted at $s$), because there is no path from $s$ to $t$ of length $d-1$. So all other spanning trees of $G$ rooted at $s$, including $T_{DFS}$, must have depth at least $d$.