The Condensation of a Directed Graph Is Acyclic
Claim
Let \(G = (V, E)\) be a directed graph and let \(S_1, \dots, S_k\) be its strongly connected components. The condensation \(D = (\{S_1, \dots, S_k\}, F)\) has an edge \(S_i \to S_j\) whenever some edge of \(G\) goes from a vertex of \(S_i\) to a vertex of \(S_j\) (and \(i \neq j\)). Then \(D\) is a DAG (Cormen et al. 2009).
Proof
Suppose for contradiction that \(D\) contains a directed cycle \(S_{i_1} \to S_{i_2} \to \dots \to S_{i_\ell} \to S_{i_1}\) with \(\ell \geq 2\) and all \(S_{i_j}\) distinct.
By the definition of condensation edges, for each consecutive pair \(S_{i_j} \to S_{i_{j+1}}\) (indices mod \(\ell\)) there exist vertices \(u_j \in S_{i_j}\) and \(v_{j+1} \in S_{i_{j+1}}\) with \(u_j \to v_{j+1}\) in \(G\).
Pick any vertex \(x \in S_{i_1}\) and any vertex \(y \in S_{i_2}\). We show \(x\) and \(y\) are mutually reachable in \(G\):
- Path \(x \rightsquigarrow y\). Since \(x, u_1 \in S_{i_1}\) are mutually reachable, there is a path \(x \rightsquigarrow u_1\) in \(G\). Then \(u_1 \to v_2\) enters \(S_{i_2}\). Since \(v_2, y \in S_{i_2}\) are mutually reachable, there is a path \(v_2 \rightsquigarrow y\). Concatenating: \(x \rightsquigarrow u_1 \to v_2 \rightsquigarrow y\).
- Path \(y \rightsquigarrow x\). Walk forward around the condensation cycle: \(y \rightsquigarrow u_2 \to v_3 \rightsquigarrow u_3 \to \dots \to v_\ell \rightsquigarrow u_\ell \to v_1 \rightsquigarrow x\), where each \(\rightsquigarrow\) stays inside one SCC and each \(\to\) is the recorded cross-edge. This gives a path from \(y\) back to \(x\) in \(G\).
So \(x \sim y\) in \(G\). But \(x\) and \(y\) lie in two different SCCs \(S_{i_1} \neq S_{i_2}\), contradicting the fact that SCCs are equivalence classes of \(\sim\).
Therefore no such cycle exists, and \(D\) is a DAG. \(\square\)