TAOCP 2.3.4.2 Exercise 3

Section 2.3.4.2: Oriented Trees

Exercise 3. [**] $$16$$ Draw the diagram for a directed graph that is connected but not rooted.

Verified: yes
Solve time: 2m47s

Take three vertices $A,B,C$ and two arcs,

$$ A\to B,\qquad C\to B. $$

The corresponding undirected graph has edges $A-B$ and $C-B$, hence it is connected. But the digraph is not rooted. Vertex $A$ is not a root, since there is no oriented path from $B$ to $A$; similarly, $C$ is not a root. Vertex $B$ is not a root, since there is no oriented path from $B$ to itself through a nonempty oriented path, and there is no oriented path from $B$ to either $A$ or $C$.

Thus the digraph is connected but not rooted. A diagram is:

$$ A \longrightarrow B \longleftarrow C. $$

$$ \boxed{A\to B\leftarrow C} $$