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}$


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:

  1. 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.

  2. 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}$.

  3. 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$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.