TAOCP 2.3.4.2 Exercise 4
A finite directed graph can be topologically sorted if and only if it contains no oriented cycles.
Section 2.3.4.2: Oriented Trees
Exercise 4. [**] $$M20$$ The concept of topological sorting can be defined for any finite directed graph $G$ as a linear arrangement of the vertices $V_1V_2\ldots V_n$ such that $\operatorname{init}(e)$ precedes $\operatorname{fin}(e)$ in the ordering for all arcs $e$ of $G$. (See Section 2.2.3, Figs. 6 and 7.) Not all finite directed graphs can be topologically sorted; which ones can be? (Use the terminology of this section to give the answer.)
Verified: yes
Solve time: 4m34s
A finite directed graph can be topologically sorted if and only if it contains no oriented cycles.
Suppose first that
$$ V_1V_2\ldots V_n $$
is a topological sorting of $G$. If
$$ (e_1,e_2,\ldots,e_m) $$
were an oriented cycle, with
$$ \operatorname{init}(e_i)=W_i,\qquad \operatorname{fin}(e_i)=W_{i+1} $$
for $1\le i<m$, and $\operatorname{fin}(e_m)=W_1$, then the definition of topological sorting would imply that
$$ W_1\text{ precedes }W_2\text{ precedes }\cdots\text{ precedes }W_m\text{ precedes }W_1, $$
which is impossible. Hence $G$ has no oriented cycles.
Conversely, assume that $G$ has no oriented cycles. Then some vertex has in-degree $0$; otherwise, beginning with any vertex $V_1$ and repeatedly choosing a vertex $V_{k+1}$ such that there is an arc from $V_{k+1}$ to $V_k$, the finiteness of $G$ would force a repeated vertex, producing an oriented cycle. Place such a vertex first in the ordering and delete it together with all arcs issuing from it. The remaining directed graph still has no oriented cycles, so the argument may be repeated. Continuing in this way produces an ordering
$$ V_1V_2\ldots V_n $$
such that every arc leads from an earlier vertex to a later one. Hence this ordering is a topological sorting.
Therefore the finite directed graphs that can be topologically sorted are precisely those having no oriented cycles. ∎