Part 8: Cycles, Connectivity & Strongly Connected Components

A Bit of History

The mathematical study of connectivity predates modern graph algorithms by decades. In 1927, Austrian mathematician Karl Menger proved what is now called Menger's theorem, connecting the maximum number of vertex-disjoint paths between two vertices to the minimum number of vertices needed to separate them — a foundational result that would later underpin the max-flow min-cut theorem (Part 15) three decades before flow networks were formalized. In 1932, American mathematician Hassler Whitney proved several structural theorems characterizing 2-connected graphs. The algorithmic side arrived much later: Robert Tarjan's 1972 paper gave linear-time algorithms for bridges, articulation points, and biconnected components, and in 1978 S. Rao Kosaraju devised the elegant two-pass DFS algorithm for strongly connected components that bears his name.

Shades of Connectivity

Part 1 defined connectivity for undirected graphs via the equivalence relation "\(u \sim v\) iff a path exists." Directed graphs need two separate notions:

• Weakly connected: the graph is connected if you ignore edge direction (treat every arc as undirected).
• Strongly connected: for every pair \(u, v\), a directed path exists from \(u\) to \(v\) and from \(v\) to \(u\).

Strong connectivity is a much stronger requirement — a one-way street network can be weakly connected (you can get anywhere ignoring direction) without being strongly connected (you might not be able to drive back the way you came).

Menger's Theorem

Strongly Connected Components

A strongly connected component (SCC) is a maximal set of vertices where every pair is mutually reachable — exactly the equivalence classes of the "mutually reachable" relation. Collapsing each SCC to a single vertex produces the condensation graph, which is always a DAG (Part 7) — a beautiful fact, since any cycle among condensed SCCs would mean those SCCs were mutually reachable and should have been merged into one.

flowchart LR
    subgraph SCC1["SCC {A,B,C}"]
        A --> B --> C --> A
    end
    subgraph SCC2["SCC {D,E}"]
        D --> E --> D
    end
    subgraph SCC3["SCC {F}"]
        F
    end
    SCC1 --> SCC2 --> SCC3
            

Kosaraju's Algorithm (Preview)

Kosaraju's algorithm finds all SCCs in \(O(V+E)\) using exactly the DFS finish-time machinery from Part 6, run twice: first a DFS on \(G\) to compute finish times, then a DFS on the transpose graph \(G^T\) (every edge reversed), processing vertices in decreasing finish-time order — each DFS tree produced in this second pass is exactly one SCC. Tarjan's SCC algorithm achieves the same result in a single DFS pass using low-link values (the same technique used for bridges below).

Bridges & Articulation Points

A bridge is an edge whose removal disconnects the graph (increases the number of components); an articulation point (or cut vertex) is a vertex whose removal does the same. Both identify single points of failure in a network, and both are found by the same DFS low-link technique: for each vertex \(v\), compute \(\text{low}[v]\) — the smallest discovery time reachable from \(v\)'s DFS subtree using at most one back edge. An edge \((u,v)\) (tree edge, \(v\) a child of \(u\)) is a bridge exactly when \(\text{low}[v] > d[u]\) — meaning \(v\)'s subtree has no way back to or above \(u\) except through that one edge.

Biconnectivity & Block-Cut Trees

A graph is 2-vertex-connected (biconnected) if it has no articulation point and remains connected after removing any single vertex. A block (or biconnected component) is a maximal biconnected subgraph. Every graph decomposes uniquely into blocks glued together at articulation points, and this decomposition has a clean tree structure: the block-cut tree, with a node for every block and every articulation point, and an edge connecting a block to each articulation point it contains. Whitney's 1932 characterizations of 2-connectivity are exactly the theorems that justify why this decomposition is well-defined.

Looking Ahead: Higher Connectivity

This part covers the connectivity concepts needed for the rest of the series' algorithmic core. A deeper structural theory exists above biconnectivity — 3-connected graphs and Tutte's Wheel Theorem (which shows every 3-connected graph can be built up from a wheel graph via a sequence of simple operations), Mader's theorems relating average degree to forced high connectivity, and the general theory of k-linked graphs and disjoint-paths problems connecting back to Menger's theorem. These form the structural backbone of graph minor theory (Part 18) and are covered there in full depth once that machinery is available.

Exercises

1. Give an example of a directed graph that is weakly connected but not strongly connected, and identify its SCCs.
2. Prove that the condensation graph of any directed graph is always acyclic (hint: proof by contradiction — what would a cycle among condensed SCCs imply about the original vertices?).
3. Find all bridges and articulation points in the graph \(A\text{-}B, B\text{-}C, C\text{-}A, C\text{-}D, D\text{-}E\) by hand, and explain your reasoning using low-link values.
4. Challenge: Construct the block-cut tree for the graph in the previous exercise, and verify that removing the articulation point(s) you found actually disconnects the graph into the blocks you identified.

Conclusion & Next Steps

Connectivity turns out to have exact, provable structure at every scale: weak versus strong for directed graphs, SCCs collapsing into a clean DAG, and bridges/articulation points/blocks decomposing any graph into its most robust pieces. With traversal, ordering, and connectivity now established, we're ready for the question most people associate with graph theory first: what's the shortest path?