TAOCP 2.3.4.2 Exercise 6

Section 2.3.4.2: Oriented Trees

Exercise 6. [**] $$M21$$ True or false: A directed graph that is rooted and contains no cycles and no oriented cycles is an oriented tree.

Verified: yes
Solve time: 2m14s

$$ \boxed{\text{True}} $$

Let $G$ be a directed graph that is rooted and contains neither cycles nor oriented cycles.

We must show that $G$ is an oriented tree.

Let $R$ be a root of $G$. By rootedness, every vertex $V\neq R$ has at least one oriented path from $V$ to $R$.

Since $G$ contains no cycles, its underlying undirected graph is a forest. In a forest there is a unique undirected path between any two vertices that lie in the same connected component.

Because every vertex has an oriented path to $R$, every vertex lies in the same connected component as $R$. Hence the underlying undirected graph is connected. A connected acyclic undirected graph is a tree. Therefore the underlying graph of $G$ is a tree.

Now consider any vertex $V\neq R$.

Since the underlying graph is a tree, there is a unique undirected path from $V$ to $R$. Because $V$ has an oriented path to $R$, that oriented path must use exactly the edges of this unique undirected path. Consequently the first edge on the path is directed away from $V$. Thus $V$ is the initial vertex of at least one arc.

Suppose $V$ were the initial vertex of two distinct arcs,

$$ V\to X,\qquad V\to Y, $$

with $X\neq Y$.

Since every vertex can reach $R$, there are oriented paths from $X$ to $R$ and from $Y$ to $R$. In the underlying tree, the unique path from $V$ to $R$ begins with a unique neighbor of $V$. Therefore at most one of $X$ and $Y$ can lie on that path. Without loss of generality, $X$ does not.

Then the oriented path

$$ V\to X\to \cdots \to R $$

together with the unique undirected path from $V$ to $R$ yields two distinct undirected paths from $V$ to $R$, contradicting the fact that the underlying graph is a tree.

Hence $V$ can be the initial vertex of at most one arc. Since it is the initial vertex of at least one arc, it is the initial vertex of exactly one arc.

Finally, $R$ cannot be the initial vertex of any arc. If $R\to W$ were an arc, rootedness would give an oriented path from $W$ to $R$. Combining $R\to W$ with that path would produce an oriented cycle, contrary to hypothesis.

Thus:

1. Every vertex $V\neq R$ is the initial vertex of exactly one arc.
2. $R$ is the initial vertex of no arc.
3. Every vertex $V\neq R$ has an oriented path to $R$.

These are precisely the defining properties of an oriented tree with root $R$.

Therefore every rooted directed graph with no cycles and no oriented cycles is an oriented tree.

$$ \boxed{\text{True}} $$