Strongly Connected Components and the Condensation DAG

Mutual Reachability in a Directed Graph

In an undirected graph, connectedness asks whether vertices can be joined by paths. In a directed graph, the direction of each edge matters: a path from \(u\) to \(v\) does not necessarily give a path from \(v\) to \(u\). Strongly connected components isolate the groups of vertices within which travel is possible in both directions. Replacing each such group by one vertex produces a simpler directed graph that records how the groups are linked.

Throughout, a directed graph is finite and has no loops or multiple directed edges. Write an edge from \(u\) to \(v\) as \(\overrightarrow{uv}\). A directed walk is a sequence \(v_0,v_1,\ldots,v_k\) such that \(\overrightarrow{v_{i-1}v_i}\) is an edge for every \(i\) from \(1\) to \(k\). A walk of length zero, consisting of one vertex, is allowed. A directed path is a directed walk with no repeated vertices. If a directed walk joins two vertices, then a directed path also joins them: whenever a vertex repeats, delete the part of the walk between two consecutive occurrences of that vertex. Repeating this deletion reduces the length until no vertex repeats.

Reachability from a vertex to itself always holds by the length-zero path. Consequently, a vertex with no incident edges is itself a strongly connected component. More generally, a singleton set is strongly connected whether or not its vertex has any outgoing edge. The definition of an SCC requires maximality, not that the component contain a cycle.

The Components Partition the Vertices

Proof. Define a relation on \(V(G)\) by \(u\sim v\) if \(u\) is reachable from \(v\) and \(v\) is reachable from \(u\). It is reflexive because each vertex has a length-zero path to itself. It is symmetric by its definition. To prove transitivity, suppose \(u\sim v\) and \(v\sim w\). There is a directed path from \(u\) to \(v\) and one from \(v\) to \(w\); concatenating them gives a directed walk from \(u\) to \(w\). Deleting any repeated-vertex portions gives a directed path from \(u\) to \(w\). The same argument using paths from \(w\) to \(v\) and from \(v\) to \(u\) gives a path from \(w\) to \(u\). Thus \(u\sim w\), so the relation is transitive.

The equivalence classes of \(\sim\) are disjoint and cover \(V(G)\). Every class is strongly connected, since any two of its vertices are mutually reachable. It is also maximal: if a strongly connected set contains a vertex \(u\) in a class, then every vertex in that set is mutually reachable with \(u\), so every such vertex lies in the same class. Thus the classes are exactly the SCCs, and they partition the vertex set. \(\square\)

This proof gives a useful way to reason about SCC membership: mutual reachability, not mere adjacency, is the test. An arc can leave a component without causing the vertices at its two ends to belong to the same component.

The Condensation Digraph

The condensation keeps the direction of travel between components and suppresses the details of travel inside each component. Edges within one SCC do not appear as loops in the condensation. Distinct original edges with the same pair of component endpoints also do not create multiple condensation edges.

Proof. Suppose, for contradiction, that \(C(G)\) has a directed cycle through distinct components \(A_1,A_2,\ldots,A_k\), where \(k\ge2\), and with edges \(A_1\to A_2,\ldots,A_{k-1}\to A_k,A_k\to A_1\). For each edge \(A_i\to A_{i+1}\), with indices taken cyclically, the definition of condensation supplies an original edge from some vertex of \(A_i\) to some vertex of \(A_{i+1}\).

Take any vertices \(x\in A_i\) and \(y\in A_j\). Following the directed cycle of components from \(A_i\) to \(A_j\), and using the corresponding original edges, gives a directed walk from a vertex of \(A_i\) to a vertex of \(A_j\). Since \(A_i\) is strongly connected, \(x\) can reach the tail of the first such edge; since \(A_j\) is strongly connected, the head of the last edge can reach \(y\). Concatenating these routes gives a directed walk, and therefore a directed path, from \(x\) to \(y\). Following the cycle in the other direction gives a directed path from \(y\) to \(x\). Thus every vertex in these components is mutually reachable with every vertex in the others. Their union is strongly connected, contradicting that the components are distinct maximal strongly connected sets. The condensation has no directed cycle, so it is a DAG. \(\square\)

The empty directed graph has no SCCs, and its condensation has no vertices or edges; it is acyclic. The proof above handles every nonempty condensation cycle, whose length must be at least two because the condensation has no loops.

Paths Between Components

Proof. Suppose first there is a directed path in \(G\) from \(u\in A\) to \(v\in B\). Record, in order, the SCC containing each vertex along this path. Whenever consecutive vertices lie in different SCCs, the original edge between them gives an edge in the condensation. Removing consecutive repetitions from the recorded sequence leaves a directed walk in \(C(G)\) from \(A\) to \(B\). Removing any repeated-vertex portions gives a directed path there.

Conversely, suppose there is a directed path of components \(A=A_0,A_1,\ldots,A_r=B\) in \(C(G)\). Each edge \(A_{i-1}\to A_i\) comes from an original edge \(\overrightarrow{x_i y_i}\), with \(x_i\in A_{i-1}\) and \(y_i\in A_i\). Within each component, any vertex can reach any other. Therefore, starting at any chosen vertex of \(A\), one can reach \(x_1\), take \(\overrightarrow{x_1y_1}\), travel within \(A_1\) to \(x_2\), and continue in this way until reaching any chosen vertex of \(B\). The resulting directed walk can be shortened to a directed path. If \(A=B\), the length-zero path in the condensation and the length-zero path from a vertex to itself in \(G\) establish the claim. \(\square\)

Worked Component and Condensation Examples

Why the Condensation Is Useful

The condensation separates two kinds of information. Inside an SCC, every vertex can reach every other, so the internal routes can be treated as a single unit when the question concerns travel between groups. Between SCCs, the condensation records which directions are possible. Because it is a DAG, it cannot contain a sequence of component-to-component dependencies that returns to its starting component.

This viewpoint is useful in directed reachability questions and in organizing a directed graph into larger regions. For example, if one needs to know whether any vertex of component \(A\) can reach any vertex of component \(B\), the proposition shows that it is enough to ask whether \(B\) is reachable from \(A\) in the condensation. It is not necessary to keep track of every internal vertex on the route.

Common Pitfall: Ignoring Edge Direction

Suppose a directed graph has vertices \(x,y\) and the single edge \(\overrightarrow{xy}\). A mistaken calculation might say “\(x\) and \(y\) are connected by an edge, so the SCC is \(\{x,y\}\).” That conclusion treats the edge as undirected. In fact, \(y\) is reachable from \(x\), but \(x\) is not reachable from \(y\). The SCCs are the singletons \(\{x\}\) and \(\{y\}\), and the condensation has the edge \(\{x\}\to\{y\}\).

The correction is to check both directions of reachability before merging vertices. Likewise, when building the condensation, retain the direction of every cross-component edge. Its acyclicity does not mean that the original graph has no directed cycles: the original graph may have many cycles inside its SCCs. It means only that there is no directed cycle among distinct SCCs.