Directed Acyclic Graphs
Directed graphs represent relationships whose direction matters: a one-way connection from \(u\) to \(v\) is different from one from \(v\) to \(u\). When these relationships contain no directed cycle, the graph is called a directed acyclic graph, or DAG. A basic structural fact is that every finite, nonempty DAG has at least one vertex where no arc enters and at least one vertex where no arc leaves. These vertices provide useful starting and ending points in the directed structure.
Throughout, a digraph is finite and has no loops or multiple copies of the same arc; both \(u\to v\) and \(v\to u\) are allowed. A directed walk of length \(\ell\) is a sequence \(v_0,v_1,\ldots,v_\ell\) such that \(v_{i-1}\to v_i\) is an arc for each \(i\) from \(1\) to \(\ell\). It is closed if \(v_0=v_\ell\). A directed cycle is a closed directed walk of length at least \(2\) whose vertices \(v_0,\ldots,v_{\ell-1}\) are distinct. The length restriction and distinctness make a directed cycle a specific kind of closed walk.
These terms describe different conditions. A source may have arcs leaving it, while a sink may have arcs entering it. A vertex with neither incoming nor outgoing arcs has both properties. In particular, an isolated vertex is both a source and a sink.
Why a Directed Walk Must Eventually Repeat
The finiteness assumption in the main result matters because it prevents us from continuing along new vertices forever. The following observation makes that precise. It will be used in both directions: following outgoing arcs detects a cycle if there is no sink, and following incoming arcs detects a cycle if there is no source.
Proof. Let the digraph have \(n\) vertices and consider a directed walk \(v_0,v_1,\ldots,v_n\), which lists \(n+1\) vertices. Since there are only \(n\) possible vertices, at least two entries are equal. To see the cycle conclusion, take the first index \(j\) at which a vertex repeats, and let \(i<j\) satisfy \(v_i=v_j\). By the choice of \(j\), the vertices \(v_i,\ldots,v_{j-1}\) are distinct. The segment \(v_i,v_{i+1},\ldots,v_j=v_i\) follows directed arcs and is closed. There are no loops, so \(j-i\ge2\); this segment is a directed cycle. \(\square\)
The lemma does not say that every directed walk in a finite digraph is a cycle. It says that a sufficiently long walk repeats a vertex, and that the portion between suitable repeated occurrences forms a directed cycle. For a DAG, this rules out any process that can keep following arcs indefinitely.
Every Finite Nonempty DAG Has a Source and a Sink
Proof. Let \(G\) be a finite nonempty DAG, and write \(n=|V(G)|\), so \(n\ge1\). First suppose, for contradiction, that \(G\) has no sink. Then every vertex has out-degree at least \(1\). Choose any \(v_0\in V(G)\). Since \(v_0\) has an outgoing arc, choose \(v_1\) with \(v_0\to v_1\). Continuing in this way gives a directed walk \(v_0,v_1,\ldots,v_n\): at each step the current vertex has an outgoing arc. The lemma gives a directed cycle in this walk, contradicting that \(G\) is acyclic. Thus \(G\) has a sink.
Now suppose, for contradiction, that \(G\) has no source. Then every vertex has in-degree at least \(1\). Choose any \(v_0\in V(G)\). Since an arc enters \(v_0\), choose \(v_1\) with \(v_1\to v_0\), then choose \(v_2\) with \(v_2\to v_1\), and continue to obtain \(v_n\to v_{n-1}\to\cdots\to v_0\). Read in the direction of the arcs, this is a directed walk of length \(n\). The lemma again gives a directed cycle, contradicting acyclicity. Hence \(G\) has a source as well. The proof requires nonemptiness to choose \(v_0\), and finiteness to force a repeated vertex. \(\square\)
The theorem asserts existence, not uniqueness: a DAG may have several sources and several sinks. It also does not require the graph to be connected. If the digraph has several components, the argument still applies to the entire vertex set; an isolated vertex, when present, already supplies both a source and a sink.
Worked Example: One Source and One Sink
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e\}\) and arcs \(E=\{a\to b,a\to c,b\to c,b\to d,c\to e,d\to e\}\). Find its sources and sinks, and verify that it is a DAG.
Count incoming and outgoing arcs at each vertex. For example, \(a\) has no entering arcs and two leaving arcs, while \(c\) has two entering arcs, \(a\to c\) and \(b\to c\), and one leaving arc, \(c\to e\).
| Vertex | Incoming arcs | \(d^-(v)\) | Outgoing arcs | \(d^+(v)\) |
|---|---|---|---|---|
| \(a\) | none | 0 | \(a\to b,a\to c\) | 2 |
| \(b\) | \(a\to b\) | 1 | \(b\to c,b\to d\) | 2 |
| \(c\) | \(a\to c,b\to c\) | 2 | \(c\to e\) | 1 |
| \(d\) | \(b\to d\) | 1 | \(d\to e\) | 1 |
| \(e\) | \(c\to e,d\to e\) | 2 | none | 0 |
Thus \(a\) is the only source and \(e\) is the only sink. To check acyclicity independently of the degree table, assign the values \(0,1,2,2,3\) to \(a,b,c,d,e\), respectively. Along every arc the value strictly increases: the arcs go from value \(0\) to \(1\) or \(2\), from \(1\) to \(2\), or from \(2\) to \(3\). A directed cycle would have to return to its starting vertex, so the value would have to increase and then return to its starting value, which is impossible.
Check: the table gives five vertices with total out-degree \(2+2+1+1+0=6\), equal to the six listed arcs; the total in-degree is \(0+1+2+1+2=6\) as well. The identified source has in-degree \(0\), and the identified sink has out-degree \(0\), as required by their definitions.
Worked Example: Several Components and an Isolated Vertex
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5,6\}\) and arcs \(E=\{1\to2,3\to4,3\to5\}\). Determine all sources and sinks. The graph has separate pieces: one arc from \(1\) to \(2\), two arcs leaving \(3\), and the isolated vertex \(6\).
The degrees are as follows. Vertex \(1\) has in-degree \(0\) and out-degree \(1\); vertex \(2\) has in-degree \(1\) and out-degree \(0\). Vertex \(3\) has in-degree \(0\) and out-degree \(2\); vertices \(4\) and \(5\) each have in-degree \(1\) and out-degree \(0\). Vertex \(6\) has in-degree \(0\) and out-degree \(0\).
| Vertex | \(d^-(v)\) | \(d^+(v)\) | Role |
|---|---|---|---|
| \(1\) | 0 | 1 | source |
| \(2\) | 1 | 0 | sink |
| \(3\) | 0 | 2 | source |
| \(4\) | 1 | 0 | sink |
| \(5\) | 1 | 0 | sink |
| \(6\) | 0 | 0 | source and sink |
The sources are \(\{1,3,6\}\), and the sinks are \(\{2,4,5,6\}\). This digraph is acyclic: each arc is one of the three listed arcs, and none leaves \(2,4,5,\) or \(6\), so no directed walk can return to its starting point. The result illustrates why one should not expect a unique source or sink, and why an isolated vertex must be counted as both.
Check: the total out-degree is \(1+0+2+0+0+0=3\), matching the three arcs. The total in-degree is \(0+1+0+1+1+0=3\), also matching the arc count. The vertices with out-degree \(0\) are exactly \(2,4,5,6\), and those with in-degree \(0\) are exactly \(1,3,6\).
Worked Example: A Directed Cycle Has No Source or Sink
Let \(H=(V,E)\) have \(V=\{p,q,r\}\) and arcs \(E=\{p\to q,q\to r,r\to p\}\). Each vertex has one entering arc and one leaving arc: \(p\) receives \(r\to p\) and sends \(p\to q\); \(q\) receives \(p\to q\) and sends \(q\to r\); \(r\) receives \(q\to r\) and sends \(r\to p\). Thus every vertex has in-degree \(1\) and out-degree \(1\).
There is no source because no vertex has in-degree \(0\), and there is no sink because no vertex has out-degree \(0\). The walk \(p,q,r,p\) is a directed cycle, so \(H\) is not a DAG. This example does not contradict the theorem: its acyclicity hypothesis fails.
Check: the three in-degrees sum to \(1+1+1=3\), and the three out-degrees sum to \(1+1+1=3\); both totals equal the three arcs. The absence of both a source and a sink is consistent with the presence of the directed cycle.
What the Structure Tells Us
The source and sink theorem gives a simple way to detect one consequence of acyclicity. In a finite digraph, if every vertex has an outgoing arc, repeatedly following an outgoing arc must eventually create a directed cycle. Therefore, if the digraph is acyclic, at least one vertex must have no outgoing arc. Reversing the direction of this reasoning gives a vertex with no incoming arc. This argument relies on finiteness; in an infinite digraph, following arcs need not repeat a vertex.
It is important not to reverse the theorem incorrectly. Having a source and a sink does not by itself imply that a digraph is acyclic. For example, take vertices \(\{s,p,q,r,t\}\) and arcs \(s\to p,p\to q,q\to p,q\to r,r\to t\). Here \(s\) is a source and \(t\) is a sink, but \(p\to q\to p\) is a directed cycle. Sources and sinks are guaranteed in a DAG, but their presence alone does not certify that the whole digraph is a DAG.
A frequent mistake is also to confuse “no incoming arc” with “no outgoing arc.” In the three-vertex cycle above, each vertex has both kinds of arcs, so none is a source or sink. In the first worked example, \(a\) has outgoing arcs and is still a source; \(e\) has incoming arcs and is still a sink. Always test the correct degree: sources have \(d^-(v)=0\), and sinks have \(d^+(v)=0\).
Check Your Understanding
Use the definitions and the finite-walk argument to answer the following questions.
- For \(V=\{u,v,w\}\) and \(E=\{u\to v,u\to w\}\), list all sources and sinks. Is this digraph acyclic? Explain.
- Give the in-degree and out-degree of each vertex in the directed cycle with vertices \(\{1,2,3,4\}\) and arcs \(1\to2,2\to3,3\to4,4\to1\). Does it have a source or sink?
- In the proof of the theorem, why does the absence of a sink let us continue constructing a directed walk at every step?
- Explain why the theorem requires the digraph to be nonempty, and why the proof uses finiteness.
- Can a vertex be both a source and a sink? State what this means about its incident arcs.