Lesson 6

Now, we are ready to prove that every directed acyclic graph can be topologically ordered.

Theorem. A directed graph has a topological ordering if and only if it is acyclic.

Proof. If the graph has a cycle, then it clearly cannot be topologically ordered. It remains to show that if the given graph is acyclic, then there exists a topological ordering of its nodes. Such an ordering can be constructed as follows. Since the graph is acyclic, it has a sink. It is safe to make this sink node the last one in the ordering. Thus, we proceed as follows: put the sink node to the end of the ordering, remove it from the graph (this keeps the graph acyclic), and repeat.◼