The Claim and Its Ingredients
A topological order puts the vertices of a digraph in a sequence in which every directed edge points from an earlier vertex to a later one. The central question is whether this ordering condition is merely a useful way to describe some acyclic digraphs, or whether it captures acyclicity exactly. The equivalence matters because it turns a structural property—having no directed cycle—into an ordering condition that can be checked directly.
Throughout, a digraph \(D=(V,A)\) is finite and has no loops or repeated arcs. An arc from \(u\) to \(v\) is written \(u\to v\). A directed walk is a sequence \(v_0,v_1,\ldots,v_\ell\) such that \(v_{i-1}\to v_i\) is an arc for every \(i\). A directed cycle is a directed closed walk of positive length whose vertices, apart from the repeated first and last vertex, are distinct. With loops excluded, a directed cycle has length at least two. A digraph is acyclic if it contains no directed cycle. A source is a vertex with in-degree zero.
Equivalently, if \(\pi(v_i)=i\) records the position of \(v_i\), then every arc \(u\to v\) must satisfy \(\pi(u)<\pi(v)\). This position inequality is the key to both directions of the proof.
A Closed Walk Contains a Directed Cycle
We first record the fact needed to show that a nonempty acyclic digraph has a source. A closed directed walk might revisit vertices, so it need not itself be a cycle. Choosing one of shortest positive length removes those repetitions.
Proof. Among all positive-length closed directed subwalks of the given walk, choose one of minimum length, say \(w_0,w_1,\ldots,w_k\), where \(w_k=w_0\) and \(k\geq1\). Such a choice exists because the original walk is one candidate and the possible lengths are positive integers. If \(w_i=w_j\) for some \(0\leq i<j\leq k\) other than the pair \((i,j)=(0,k)\), then the segment \(w_i,w_{i+1},\ldots,w_j\) is a positive-length closed directed subwalk of length \(j-i<k\). This contradicts the minimal choice. Thus the chosen walk has no repeated vertices other than its first and last vertex, and is a directed cycle. \(\square\)
Why an Acyclic Digraph Has a Source
Proof. Let \(D\) be nonempty and acyclic. Suppose, to obtain a contradiction, that \(D\) has no source. Then every vertex has at least one incoming arc. Choose any vertex \(x_0\). Since it is not a source, choose \(x_1\) with \(x_1\to x_0\); then choose \(x_2\) with \(x_2\to x_1\), and continue. This produces a sequence in which each next vertex points to the preceding one. Since \(D\) has finitely many vertices, some vertex repeats: there are indices \(i<j\) with \(x_i=x_j\). The arcs \(x_j\to x_{j-1}\to\cdots\to x_i\) then form a positive-length closed directed walk. By the preceding lemma, this walk contains a directed cycle, contradicting acyclicity. Therefore \(D\) has a source. \(\square\)
Finiteness is essential to this argument: it guarantees a repeated vertex in the sequence. The lemma applies not only to the original digraph but also to any nonempty induced subdigraph of an acyclic digraph. Indeed, a directed cycle in an induced subdigraph would also be a directed cycle in the original digraph.
Proof of the Characterization
Proof of the theorem. First suppose \(D\) has a topological order \(v_1,\ldots,v_n\). If \(D\) had a directed cycle \(v_{i_1}\to v_{i_2}\to\cdots\to v_{i_k}\to v_{i_1}\), the topological-order condition would give \(\pi(v_{i_1})<\pi(v_{i_2})<\cdots<\pi(v_{i_k})<\pi(v_{i_1})\). By transitivity of \(<\), this implies \(\pi(v_{i_1})<\pi(v_{i_1})\), which is impossible. Thus \(D\) is acyclic.
Conversely, suppose \(D\) is acyclic. We prove by induction on \(n=|V|\) that \(D\) has a topological order. For \(n=0\), the empty listing is a topological order because there are no arcs to check. Now let \(n\geq1\), and assume the statement holds for every acyclic digraph with fewer than \(n\) vertices. By the source lemma, \(D\) has a source \(s\). Delete \(s\) and all arcs incident with it, obtaining the induced digraph \(D-s\) on \(n-1\) vertices. This smaller digraph is acyclic: any directed cycle in it would also be a directed cycle in \(D\). By the induction hypothesis, \(D-s\) has a topological order \(u_1,\ldots,u_{n-1}\). Put \(s\) first, giving \(s,u_1,\ldots,u_{n-1}\). Every arc of \(D\) either has both endpoints in \(D-s\), in which case it points forward by the order there, or has \(s\) as an endpoint. No arc enters \(s\), since \(s\) is a source, so any arc incident with \(s\) points from \(s\) to a later vertex. Hence the new listing is a topological order of \(D\). This completes the induction and proves both directions. \(\square\)
The proof gives a construction as well as an existence argument: choose a source, place it first, and repeat on the remaining digraph. At every stage the remaining induced digraph is acyclic, so the source lemma continues to apply until no vertices remain. The specific choices of sources need not be unique; any permitted choice gives a valid order.
Worked Examples
Worked Example: Constructing an Order by Removing Sources
Let \(D=(V,A)\) have \(V=\{a,b,c,d,e\}\) and \(A=\{a\to b,\ a\to c,\ b\to d,\ c\to d,\ d\to e\}\). Remove sources successively and record the resulting order.
| Remaining vertices | Sources at this stage | Chosen source |
|---|---|---|
| \(\{a,b,c,d,e\}\) | \(\{a\}\) | \(a\) |
| \(\{b,c,d,e\}\) | \(\{b,c\}\) | \(b\) |
| \(\{c,d,e\}\) | \(\{c\}\) | \(c\) |
| \(\{d,e\}\) | \(\{d\}\) | \(d\) |
| \(\{e\}\) | \(\{e\}\) | \(e\) |
Initially, \(a\) is the only source because the arcs into \(b\) and \(c\) come from \(a\), the arcs into \(d\) come from \(b,c\), and the arc into \(e\) comes from \(d\). After removing \(a\), both \(b\) and \(c\) have in-degree zero. Choosing \(b\) leaves \(c\) as the only source; after removing \(c\), \(d\) has no incoming arc from a remaining vertex, and then \(e\) does as well. The resulting order is \(a,b,c,d,e\).
Check: The five arcs point forward in this listing: \(a\to b\) has positions \(1<2\), \(a\to c\) has \(1<3\), \(b\to d\) has \(2<4\), \(c\to d\) has \(3<4\), and \(d\to e\) has \(4<5\). Thus the constructed listing satisfies the definition.
Worked Example: Different Choices Can Give Different Orders
Let \(D=(V,A)\) have \(V=\{p,q,r,s\}\) and \(A=\{p\to r,\ q\to r,\ q\to s\}\). The vertices \(p\) and \(q\) are both sources initially. Choose \(q\) first. After deleting \(q\), the remaining vertices are \(\{p,r,s\}\), and \(p\) is a source. Delete \(p\); then \(r\) and \(s\) are both sources. Choosing \(s\) before \(r\) gives the order \(q,p,s,r\).
Check: The positions are \(\pi(q)=1\), \(\pi(p)=2\), \(\pi(s)=3\), and \(\pi(r)=4\). The arc \(p\to r\) satisfies \(2<4\), \(q\to r\) satisfies \(1<4\), and \(q\to s\) satisfies \(1<3\). Every arc points forward. Isolated vertices, if present, also cause no difficulty: they have in-degree zero and no arc imposes an ordering constraint on them.
Worked Example: A Source Does Not Guarantee Acyclicity
Let \(D=(V,A)\) have \(V=\{s,a,b,c\}\) and \(A=\{s\to a,\ a\to b,\ b\to c,\ c\to a\}\). The vertex \(s\) is a source, but \(a\to b\to c\to a\) is a directed cycle. Removing \(s\) leaves that cycle intact.
If a topological order existed, the three cycle arcs would require \(\pi(a)<\pi(b)\), \(\pi(b)<\pi(c)\), and \(\pi(c)<\pi(a)\). Combining them gives \(\pi(a)<\pi(a)\), a contradiction. Thus the digraph has a source but has no topological order; the theorem requires acyclicity, not merely the existence of one source.
Check: The cycle uses the arcs \(a\to b\), \(b\to c\), and \(c\to a\), all of which are in \(A\), and its vertices \(a,b,c\) are distinct. The source \(s\) does not belong to this cycle and cannot remove the obstruction.
Common Pitfalls and Why the Result Matters
A common incorrect argument is: “There is a source, so the digraph is acyclic.” The third example disproves this. A source is guaranteed by acyclicity, but a cyclic digraph may also have sources elsewhere. In the proof, the crucial point is that after removing a source from an acyclic digraph, the remaining digraph is still acyclic. That fact allows source removal to continue at every nonempty stage.
Another mistake is to check only that each vertex appears once in a proposed order. A listing is not topological unless every arc points forward. For example, in the first example, \(a,d,b,c,e\) lists all five vertices, but the arc \(b\to d\) points from position \(3\) to position \(2\), so this listing fails.
The characterization is useful because it gives two ways to establish the same property. To prove a digraph is acyclic, one may provide a topological order and check each arc. To prove that an acyclic digraph has such an order, source existence and induction provide a construction and explain why it must succeed. If the process ever reaches a nonempty remaining digraph with no source, the source lemma shows that this remaining digraph contains a directed cycle; that is exactly where the acyclicity hypothesis has failed.
Check Your Understanding
For each question, use the position condition for a topological order and the source-removal proof.
- Why does a directed cycle make a topological order impossible? Write the chain of position inequalities for a cycle of length four.
- In the induction proof, why is \(D-s\) acyclic when \(D\) is acyclic?
- Give an explicit topological order for the digraph with \(V=\{1,2,3,4\}\) and \(A=\{1\to3,\ 2\to3,\ 3\to4\}\). Verify every arc by positions.
- Can a digraph with a source contain a directed cycle? Use an explicit vertex and arc set to justify your answer.
- Explain why the empty digraph has a topological order and how it fits the induction proof.