Inspiration: CS61BL Lab 14 — Topological Sort, "Discussion: Topological Sorts and DAG's" (cs61bl.org/labs/lab14)

1. The Question

Why can topological sort only be performed on DAGs (directed acyclic graphs)? And given a DAG, why does one always exist? The full answer has two directions:

• DAG ⇒ a topological ordering exists (proved constructively — the proof is Kahn's algorithm)
• Cycle ⇒ no topological ordering can exist (short contradiction)

The existence proof has three moving parts: a lemma (an in-degree-0 vertex always exists), a termination argument (the peeling process never gets stuck), and a correctness argument (the peeled order respects every edge). Each part is below.

2. Lemma: Every Finite Nonempty DAG Has an In-Degree-0 Vertex

This step is not free — it's exactly where acyclicity gets used, so it deserves its own proof. The constructive version (nicer than contradiction):

Pick any vertex. Walk backwards along in-edges: from the current vertex, step to any predecessor (any vertex with an edge pointing into the current one). Two cases:

1. If this backward walk could continue forever, then since the graph is finite, by pigeonhole we'd eventually revisit some vertex — but revisiting means the walk traced out a cycle. Contradiction with acyclicity.
2. So the walk must halt at some vertex with no predecessor to step to — i.e., a vertex with in-degree 0. ∎

Both hypotheses are load-bearing: finite rules out an infinite backward chain, acyclic rules out looping. (Equivalent phrasing: take a maximal-length path; its start vertex must have in-degree 0, else the path could be extended or a cycle exists.)

3. The Peeling Process — Why It Never Gets Stuck

The construction: find an in-degree-0 vertex v (lemma), append it to the output, delete v and all its out-edges, repeat.

Key observation: deleting vertices/edges can only destroy cycles, never create them. A cycle is a set of edges; removing things can't produce one. So after peeling v, the remaining graph is still a DAG — which means the lemma applies to it again, and another in-degree-0 vertex exists.

Each round removes exactly one vertex, the graph is finite, so the process runs exactly n rounds and outputs all n vertices. Formally this is induction on n: the base case is trivial, and the inductive step is "peel one vertex, invoke the hypothesis on the (n−1)-vertex DAG that remains."

4. Correctness — Why the Peeled Order Is a Valid Topological Sort

This is the crux, and it's not automatic — it depends entirely on peeling only in-degree-0 vertices.

Claim. For every edge u → w, vertex u leaves before w.

Proof. As long as u has not been peeled, the edge u → w still exists in the remaining graph, so w's current in-degree is at least 1 — meaning w is ineligible for peeling. So w can only be peeled after all of its predecessors (including u) have been peeled and taken their edges with them. Hence u precedes w in the output. Since this holds for every edge, the sequence is a valid topological sort. ∎