TAOCP 2.3.4.2 Exercise 15

Exercise 15. [**] $$M20$$ True or false: A directed graph that is connected and balanced is strongly connected.

Verified: yes
Solve time: 1m04s

True.

Let $G$ be a finite directed graph that is connected and balanced, with no isolated vertices. By Theorem G, $G$ possesses an Eulerian trail $P=(e_1,\ldots,e_m)$ with $\operatorname{fin}(e_m)=\operatorname{init}(e_1)$, so $P$ is a closed oriented walk that uses every arc exactly once.

Let $V$ and $V'$ be vertices of $G$. Since $G$ has no isolated vertices, each occurs as the initial vertex of some arc in $P$, hence each occurs at least once as a vertex along the sequence of endpoints of $P$. Choose an occurrence of $V$ along $P$. Following the directed walk $P$ from that occurrence eventually reaches every subsequent vertex along the sequence, and in particular an occurrence of $V'$, since $P$ traverses all arcs and returns to its starting point. This gives an oriented path from $V$ to $V'$. The same argument applied in the cyclic continuation of $P$ shows that every vertex is reachable from every other vertex.

Hence $G$ is strongly connected.

This completes the proof. ∎