Existence of a Topological Ordering

A topological order requires every edge to point from earlier to later in the order.

Consider what a cycle would force on the ordering of its vertices.

1. 1. Show a cycle prevents ordering

   If a cycle exists, some vertex in it would need to come both before and after another vertex in the cycle, which is impossible in a linear order.

2. 2. Show acyclicity suffices

   Conversely, any directed acyclic graph has at least one vertex with no incoming edges; repeatedly removing such a vertex and its edges produces a valid topological order, so a topological ordering exists exactly for DAGs.

Answer: Exactly when it is a directed acyclic graph.