Directed Graphs and Digraphs

(Double counting.) Consider the set of pairs

We count $|S|$ two ways. First, group by vertex $v$: for fixed $v$, the number of edges $e$ with tail $v$ is by definition $\deg^+(v)$. Since every edge has exactly one tail, each edge $e$ contributes to $S$ exactly once, paired with its unique tail. Summing over all vertices,

Second, group by edge $e$: for each $e \in E$, there is exactly one vertex $v$ (its tail) with $(v,e) \in S$, so each edge contributes exactly one pair. Hence

Combining the two counts gives $\sum_{v} \deg^+(v) = |E|$. The identical argument applied to heads instead of tails (using $\deg^-(v)$, the number of edges with head $v$) gives $\sum_v \deg^-(v) = |E|$. $\blacksquare$

Equivalence relation. We check the three properties directly. Reflexive: for any $v \in V$, the length-0 walk from $v$ to $v$ is a directed path (vacuously, with no edges), so $v \sim v$. Symmetric: if $u \sim v$, then by definition there is a directed path from $u$ to $v$ and one from $v$ to $u$; this is a symmetric statement in $u,v$, so $v \sim u$. Transitive: suppose $u \sim v$ and $v \sim w$. Then there are directed paths $P_1: u \to v$, $P_2: v \to w$, $P_3: v \to u$, $P_4: w \to v$. Concatenating the walk $P_1$ followed by $P_2$ gives a directed walk from $u$ to $w$ (walks may repeat vertices, so concatenation of two walks is always a walk); every directed walk from $u$ to $w$ contains a directed path from $u$ to $w$ as a subsequence (delete a chord: if a vertex repeats in the walk, excise the loop between the repetitions and repeat until all vertices are distinct — this terminates since the walk is finite and each excision strictly shortens it). Hence a directed path $u \to w$ exists. Symmetrically, concatenating $P_4$ then $P_3$ gives a directed walk from $w$ to $u$, and hence a directed path $w \to u$. Thus $u \sim w$. Since $\sim$ is an equivalence relation on the finite set $V$, its equivalence classes partition $V$ (this is the standard fact that equivalence classes of an equivalence relation partition the underlying set — every element lies in its own class, and two classes are either equal or disjoint by transitivity and symmetry).

Condensation is acyclic. Suppose toward a contradiction that $D^*$ contains a directed cycle

where $A_0, \dots, A_{k-1}$ are distinct SCCs of $D$ (distinct because a directed cycle in $D^*$, as a digraph, is defined to have distinct vertices among $A_0,\dots,A_{k-1}$). By definition of the condensation's edges, for each $i$ there exist vertices $a_i \in A_i$, $a_i' \in A_{i+1 \bmod k}$ with $(a_i, a_i') \in E$. Also, since $A_{i+1}$ is a single SCC, any two of its vertices are $\sim$-equivalent, so there is a directed path inside $D$ from $a_i'$ to any other chosen vertex of $A_{i+1}$, in particular to $a_{i+1}$ (the vertex we use to leave $A_{i+1}$ next). Chaining these edges and paths together over $i = 0, 1, \dots, k-1$ produces a directed walk in $D$ starting and ending in $A_0$, and passing through at least one vertex of every $A_i$. If $k \geq 2$, this walk visits a vertex of $A_0$ (say $a_0$ or the return point in $A_0$) and later a vertex of $A_1$, and eventually returns to $A_0$: extracting the sub-walk from a vertex $x \in A_0$ back to a vertex $y \in A_0$ that passes through $A_1$ gives directed walks $x \to y$ and, by reflexivity/symmetry within $A_0$'s own internal connectivity (a directed path from $y$ back to $x$ exists since $x, y \in A_0$ are $\sim$-equivalent), a directed walk $y \to x$. But we also get, by the same chaining restricted to just two indices, directed walks from a representative of $A_0$ to a representative of $A_1$ and — going the rest of the way around the cycle — back from that representative of $A_1$ to the representative of $A_0$. Converting each directed walk to a directed path as in the transitivity argument above, this shows $A_0 \sim A_1$ in the vertex sense, i.e., the representative vertices are mutually reachable, forcing $A_0$ and $A_1$ to be the same SCC. This contradicts $A_0 \neq A_1$. (The case $k=1$, a self-loop $A_0 \to A_0$ in $D^*$, is excluded by definition since condensation edges are only drawn between distinct SCCs.) Either way we reach a contradiction, so $D^*$ has no directed cycle: it is a DAG. $\blacksquare$

We prove both directions.

($\Leftarrow$) If a topological order exists, $D$ is acyclic. Suppose for contradiction $D$ has a directed cycle $v_0 \to v_1 \to \cdots \to v_{k-1} \to v_0$ with $k \geq 1$ and $v_0, \dots, v_{k-1}$ distinct. Since $(v_0,v_1), (v_1,v_2), \dots, (v_{k-2},v_{k-1})$ are all edges, applying the defining property of $\sigma$ repeatedly gives

But $(v_{k-1}, v_0)$ is also an edge, so $\sigma(v_{k-1}) < \sigma(v_0)$. Combining, $\sigma(v_0) < \sigma(v_{k-1}) < \sigma(v_0)$, a contradiction (strict inequality cannot hold with itself). Hence no directed cycle exists, and $D$ is acyclic.

($\Rightarrow$) If $D$ is acyclic, a topological order exists. We argue by strong induction on $n = |V|$. Base case $n = 0$: the empty bijection trivially satisfies the (vacuous) condition. Inductive step: Assume every acyclic digraph on fewer than $n$ vertices has a topological order, and let $D$ be acyclic with $|V| = n \geq 1$. Claim: $D$ has a vertex $s$ with $\deg^-(s) = 0$ (a source). Proof of claim: Suppose not — every vertex has in-degree at least $1$. Build a sequence by picking any starting vertex $u_0$, and having chosen $u_i$, since $\deg^-(u_i) \geq 1$ there is an edge $(u_{i+1}, u_i) \in E$ for some $u_{i+1}$; continue backward this way to define $u_0, u_1, u_2, \dots$ indefinitely (this is always possible since every vertex has an in-edge). Since $V$ is finite, by the pigeonhole principle some vertex repeats among $u_0, u_1, \dots, u_n$ (that is $n+1$ terms drawn from $n$ possible vertices): there exist $0 \le i < j \le n$ with $u_i = u_j$. The edges $(u_{j}, u_{j-1}), (u_{j-1}, u_{j-2}), \dots, (u_{i+1}, u_i)$ then form a directed cycle $u_i = u_j \to u_{j-1} \to \cdots \to u_{i+1} \to u_i$ (after discarding any earlier repeats within this segment to make vertices distinct, which is possible by the same excision argument used above, and the segment is nonempty since $i<j$). This contradicts acyclicity of $D$. This proves the claim. Now let $s$ be a source of $D$, and let $D' = D - s$ be the digraph obtained by deleting $s$ and all edges incident to it. $D'$ is acyclic: any directed cycle in $D'$ would also be a directed cycle in $D$ (it uses only edges of $D$ that were already present), contradicting acyclicity of $D$. Also $D'$ has $n - 1$ vertices. By the inductive hypothesis, $D'$ has a topological order $\sigma' : V \setminus \{s\} \to \{1, \dots, n-1\}$. Define $\sigma : V \to \{1, \dots, n\}$ by $\sigma(s) = 1$ and $\sigma(v) = \sigma'(v) + 1$ for $v \neq s$. This is a bijection onto $\{1,\dots,n\}$ since $\sigma'$ is a bijection onto $\{1,\dots,n-1\}$ and $1$ is used exactly once (by $s$). Check the ordering condition on every edge $(u,v) \in E$:

• If $u = s$: since $s$ has in-degree $0$, $u \ne s$'s constraint is irrelevant here we need $\sigma(s) < \sigma(v)$, i.e. $1 < \sigma(v)$, which holds since $v \ne s$ (no edge from $s$ to $s$, as $D$ is simple/loop-free) forces $\sigma(v) = \sigma'(v)+1 \geq 2 > 1$.
• If $u \neq s$: then also $v \neq s$, because $s$ has in-degree $0$ so no edge has head $s$. Both $u,v \neq s$ means $(u,v)$ is an edge of $D'$ too (it survives deletion of $s$), so $\sigma'(u) < \sigma'(v)$ by the inductive hypothesis, hence $\sigma(u) = \sigma'(u)+1 < \sigma'(v)+1 = \sigma(v)$.

In both cases $\sigma(u) < \sigma(v)$, completing the induction. $\blacksquare$