# Proving Depth First Search

Let G be a connected graph, and let r ∈ V (G). Prove that G has a spanning tree T such that for every edge of G with ends u and v, either u belongs to the unique path in T with ends v and r, or v belongs to the unique path in T with ends u and r.

This is the problem I have, but I don't really know how to go about actually proving it. It seems like if the graph is connected then it should automatically be true that there is a path as stated, but I don't know where to go from there.

• It is a property of the spanning tree found by depth first search. – Salomo Apr 28 '15 at 2:29

In CLRS Introduction to Algorithms, this is basically Theorem 22.10. Let $T$ be the spanning tree obtained from performing a depth first search on $G$ starting at $r$. Then there are two cases for an edge $(u,v)$. Without loss of generality, $v$ was visited after $u$.
1. If $(u,v)$ is followed in the $u\to v$ direction, then $v$ must have been undiscovered at that point because otherwise the edge would already have been followed in the other direction. Thus $(u,v)$ is an edge in $T$, and so $u$ is in the unique path from $r$ to $v$ in $T$. (It is a "tree edge.")
2. If $(v,u)$ is followed in the $v\to u$ direction, then the edge is not part of $T$, but because this edge exists it must be that $v$ was visited before $u$ was finished, so $u$ is in the unique path from $r$ to $v$ in $T$. (It is a "back edge.")