1
$\begingroup$

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.

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

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.")

$\endgroup$

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.