Lesson 5

Lemma. Every directed acyclic graph has a node that is a sink. Proof. Consider a DAG and assume, for the sake of contradiction, that it contains no sinks. Let \(v\) be its node. Since \(v\) is not a sink, the graph must contain an edge going out of \(v\), call it \((v, u)\). Now, focus on \(u\). It is also not a sink, hence there must exist an edge \((u, w)\). Continuing in the same fashion, we construct a walk of the following form: \[v \to u \to w \to \dotsb .\] A simple, but crucial observation: since the graph has a finite number of nodes, some node \(a\) will eventually repeat in this walk: \[v \to u \to w \to \dotsb \to a \to \dotsb \to a \to \dotsb.\] But this means that the graph has a cycle, a contradiction.◼

It should be noted that a cyclic graph may also contain a sink, but it can also be sink-free. For example, the left cyclic graph below does not have a sink, whereas in the right graph the node \(2\) is a sink.