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$.
I can't figure this problem out or even know what it is asking for. Can we try to prove this using contradiction? Assume $u$ belongs to the path $T$ with ends $v$ and $r$ "and" $v$ belongs to the path in $T$ with ends $u$ and $r$. Thus there exists a cycle in the spanning tree T which is a contradiction. Does this work? Any solutions or hints are greatly appreciated.
The 'either' here is ambiguous, and I hate it when they do this.
For some, "either A or B" means just "A or B" (at least one, but it could be both). For others, "either A or B" means "A exclusive-or B" (at least one, but not both).
So the minimum would be to prove that at least one of the two holds.
Actually in this case, it's and exclusive-or, so let's prove that exactly one holds.
Let's not care about spanning trees and show that the statement holds for any tree $T$.
We first show that $u$ is on the $v-r$ path, or $v$ is on the $u-r$ path (simple 'or'). Let $uu_1u_2 \ldots u_kr$ be the unique path between $u$ and $r$. If this path contains $v$, then the statement holds ($v$ is on the $u-r$ path). Otherwise, look at the path $vuu_1 \ldots u_kr$. It is the unique $v-r$ path, and it contains $u$.
But actually, this also shows that both cannot hold. Say that the $u-r$ path contains $v$ (without loss of generality), and let $uu_1 \ldots u_kv v_1 \ldots v_jr$ be this path (actually $u_1 = v$, but let's not bother proving this).
Then $vv_1 \ldots v_jr$ is the unique $v-r$ path, and it does not contain $u$.