TAOCP 2.3.4.2 Exercise 13
Let $G$ be a directed graph, possibly infinite, and let $R$ be a root of $G$.
Section 2.3.4.2: Oriented Trees
Exercise 13. [**] $$M24$$ Prove that if $R$ is a root of a (possibly infinite) directed graph $G$, then $G$ contains an oriented subtree with the same vertices as $G$ and with root $R$. (As a consequence, it is always possible to choose the free subtree in flow charts like Fig. 32 of Section 2.3.4.1 so that it is actually an oriented subtree; this would be the case in that diagram if we had selected $e''{13}$, $e''{19}$, $e_{20}$, and $e_{17}$ instead of $e'{13}$, $e'{19}$, $e_{23}$, and $e_{15}$.)
Verified: no
Solve time: 3m46s
Let $G$ be a directed graph, possibly infinite, and let $R$ be a root of $G$. Thus for every vertex $V$ there exists a finite directed path from $V$ to $R$.
For each vertex $V\neq R$, choose one directed path
$$ P(V):\qquad V=V_0\to V_1\to\cdots\to V_k=R . $$
Let $e[V]$ be the first arc of $P(V)$, namely $V\to V_1$.
Define $T$ to be the spanning subgraph of $G$ having all vertices of $G$ and exactly the arcs $e[V]$ for $V\neq R$.
We shall prove that $T$ is an oriented tree with root $R$.
First, every vertex $V\neq R$ is the initial vertex of exactly one arc of $T$, namely $e[V]$. Also, $R$ is the initial vertex of no arc of $T$. Hence conditions (a) and (b) in the definition of oriented tree are satisfied.
It remains to verify condition (c).
For any vertex $V$, let
$$ V=x_0,\ x_1,\ x_2,\ldots $$
be the sequence obtained by repeatedly following the selected arcs of $T$:
$$ e[x_i]: x_i\to x_{i+1}. $$
If some $x_i=R$, the sequence terminates there.
We first show that every such sequence eventually reaches $R$.
Assume the contrary. Then there exists a vertex $V$ for which the sequence
$$ x_0,x_1,x_2,\ldots $$
never reaches $R$.
Since $P(x_0)$ is a finite path from $x_0$ to $R$, let its length be $n$. We prove by induction on $i$ that $x_i$ lies on $P(x_0)$.
For $i=0$ this is obvious.
Suppose $x_i$ lies on $P(x_0)$, say $x_i=u$. The selected arc $e[u]$ is the first arc of the chosen path $P(u)$. Since $P(u)$ is a path from $u$ to $R$, its first step goes to a vertex that occurs after $u$ on the path $P(x_0)$. Therefore $x_{i+1}$ is a later vertex of $P(x_0)$. Thus the induction goes through.
Consequently all vertices $x_i$ lie on the finite path $P(x_0)$, which contains only $n+1$ vertices. Since the sequence never reaches $R$, infinitely many terms occur among the first $n$ vertices of $P(x_0)$. Hence some vertex appears twice:
$$ x_p=x_q,\qquad p<q. $$
Because every vertex of $T$ has at most one outgoing arc, the sequence is uniquely determined by its current vertex. Therefore
$$ x_p,x_{p+1},\ldots,x_{q-1} $$
forms a directed cycle in $T$.
But every vertex on this cycle lies on the path $P(x_0)$, and a directed cycle cannot be contained in a finite directed path. This contradiction shows that every sequence obtained by following selected arcs must eventually reach $R$.
Now let $V\neq R$. Starting from $V$ and following selected arcs, we eventually reach $R$. Since each vertex of $T$ has exactly one outgoing arc except $R$, which has none, there is only one possible directed walk from $V$. Hence the directed path from $V$ to $R$ in $T$ is unique.
Therefore condition (c) holds: for every vertex $V\neq R$ there is a unique directed path in $T$ from $V$ to $R$.
Thus $T$ is an oriented tree with root $R$. Since $T$ contains all vertices of $G$, it is an oriented subtree of $G$ having the same vertex set as $G$.
$$ \boxed{\text{Every directed graph with root }R\text{ contains a spanning oriented subtree rooted at }R.} $$
$\square$