TAOCP 2.3.4.2 Exercise 7

Section 2.3.4.2: Oriented Trees

Exercise 7. [**] $$M22$$ True or false: A directed graph satisfying properties (a) and (b) of the definition of oriented tree, and having no oriented cycles, is an oriented tree.

Verified: yes
Solve time: 1m49s

The claim is true: any finite directed graph satisfying (a) and (b) and having no directed cycles must already be an oriented tree, because condition (c) is forced by the other assumptions.

-, Let $G$ be a finite directed graph with distinguished vertex $R$ such that:

• (a) Every vertex $V \neq R$ has exactly one outgoing arc.
• (b) $R$ has no outgoing arcs.
• The graph contains no directed cycles.

We prove that every vertex has a directed path to $R$.

-, Take any vertex $V$. If $V = R$, the claim is trivial. Assume $V \neq R$. By (a), $V$ has exactly one outgoing arc, so there is a uniquely determined sequence

$$ V = V_0 \to V_1 \to V_2 \to \cdots $$

where each $V_{i+1}$ is the unique vertex reached from $V_i$.

Because the graph is finite, this sequence cannot produce infinitely many distinct vertices. Therefore, at some stage, either:

1. A vertex repeats, or
2. The sequence terminates at a vertex with no outgoing arcs.

Case 1: If a vertex repeats, then the sequence contains a directed cycle, contradicting the hypothesis.

Case 2: The only vertex with no outgoing arcs is $R$ by (b). Hence the sequence must terminate at $R$.

Thus every starting vertex $V$ eventually reaches $R$ by following outgoing arcs. This proves condition (c): $R$ is reachable from every vertex.

-, Since:

• each $V \neq R$ has exactly one outgoing arc,
• $R$ has none,
• there are no directed cycles,
• and every vertex reaches $R$,

the graph is exactly an oriented tree rooted at $R$.

-, The key point is that in a finite directed graph with outdegree at most 1 per vertex, absence of directed cycles forces all maximal directed paths to end at the unique sink $R$, so reachability is not an independent assumption.