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).
Weak asks “is there a connection?” Strong asks “can I get there and back?”
For directed graphs, connectivity depends on whether we respect the arrows. A weakly connected graph may look like one connected road network after erasing directions, while still containing one-way dead ends. Strong connectivity requires mutual directed reachability between every pair.
Quick Mental Test
Weak: erase the arrowheads and ask whether the graph stays in one piece. Strong: keep the arrows and ask whether every trip has some directed route back.
Menger's Theorem
Preview: Paths and Cuts Are Two Sides of One Coin
Menger's theorem states: the maximum number of vertex-disjoint paths between two non-adjacent vertices \(s\) and \(t\) equals the minimum number of vertices whose removal disconnects \(s\) from \(t\) (there is a parallel edge-disjoint version too). This is a genuinely deep duality — it says "how many independent routes exist" and "how fragile the connection is" are always numerically identical, never just approximately related. We revisit this formally, and its generalization to network flow, in Part 15.
Independent routes and minimum blockers measure the same robustness
Imagine traffic from s to t has three internally vertex-disjoint routes. No single intermediate vertex can stop all traffic, and neither can any pair. To separate s from t, you must hit every independent route. Menger's theorem says this numerical match is exact in every graph.
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.
Inside an SCC, movement is reversible; between SCCs, the flow becomes one-way
SCCs are the largest regions in which directed travel is mutually possible. Once each region is compressed to a single super-vertex, all the internal cycles disappear and only the one-way relationships between components remain.
Memory Hook
SCCs are the “cycle-rich islands.” Compress each island to a dot and the remaining map always points forward like a DAG.
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).
Kosaraju uses the first DFS to choose the right doorway for the second DFS
The first pass does not identify SCCs directly. Its finish times tell us which component should be opened first after every arrow is reversed. In the transpose graph, starting from the highest-finish unassigned vertex lets DFS flood one SCC without leaking into an already-unprocessed component.
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.
A bridge is a fragile link; an articulation point is a fragile junction
Both concepts ask the same reliability question at different scales: what single removal can split the network? A bridge is the only edge carrying connectivity between two regions; an articulation point is the only vertex through which two regions communicate.
Ask whether a DFS subtree has an emergency route back upward
The low-link value of a child subtree records how high that subtree can reach without using its parent tree edge. This turns bridge detection into one simple comparison.
Articulation-Point Version
For a non-root DFS vertex u, if some child v satisfies \(\operatorname{low}[v] \ge d[u]\), that child subtree cannot reach an ancestor of u without passing through u, so u is an articulation point. The DFS root is special: it is an articulation point exactly when it has at least two DFS-tree children.
Network Reliability Analysis
Internet backbone providers and power-grid operators both run bridge/articulation-point analysis on their network topology graphs to find single points of failure — a single fiber link (bridge) or a single routing hub (articulation point) whose failure would partition the network. Modern infrastructure is deliberately designed to be 2-edge-connected (no bridges) and 2-vertex-connected (no articulation points) wherever budget allows, specifically to eliminate these single points of failure.
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.
Compress each robust block, but keep the articulation vertices as joints
A block-cut tree separates the graph into its locally robust pieces. A block node represents a maximal biconnected region; an articulation node represents a shared vertex where blocks meet. The resulting structure alternates between these two node types and forms a tree.
How to Read the Tree
Block nodes never connect directly to block nodes, and articulation nodes never connect directly to articulation nodes. The tree alternates block → cut vertex → block, making the graph's global vulnerability structure easy to see.
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
- Give an example of a directed graph that is weakly connected but not strongly connected, and identify its SCCs.
- 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?).
- 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.
- 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?
Next in the Series
In Part 9: Shortest Paths I — Dijkstra & Bellman-Ford, we unify every shortest-path algorithm in this series under one relaxation framework and meet difference constraints.