Cuts, connectivity, and Menger's theorem

Fix distinct vertices $s$ and $t$ in a finite simple undirected graph. An $s$–$t$ edge cut is a set of edges whose removal leaves no path from $s$ to $t$. For a vertex subset $S$ containing $s$ but not $t$, its edge boundary consists of edges with one endpoint in $S$ and one outside. Every $s$–$t$ path crosses that boundary. Edge-disjoint paths share no edges, though they may pass through the same intermediate vertices.

An internal vertex separator instead removes vertices other than $s$ and $t$, together with their incident edges. Internally vertex-disjoint paths share only the two endpoints. In the usual local vertex form of Menger's theorem, $s$ and $t$ must be nonadjacent: if a direct edge joined them, deleting only other vertices could never remove that one-edge route. Endpoint failures are deliberately excluded; allowing removal of $s$ would make every separator problem trivial.

If there are $k$ edge-disjoint $s$–$t$ paths, deleting fewer than $k$ edges cannot destroy them all. Each removed edge can meet at most one of those paths. Therefore the maximum number of edge-disjoint paths is at most the minimum edge-cut size. Menger's edge theorem asserts equality. The internal-vertex version makes the same equality for internally vertex-disjoint paths and internal separators, assuming the endpoints are nonadjacent. These statements apply even when no path exists, in which case both values are zero.

We state the full equality theorem here and develop its algorithmic link through integral flows in a later lesson. It is already valuable as a certificate method: display $k$ disjoint paths and a separator of size $k$. The paths prove no smaller separator works; the separator proves no larger disjoint family exists. Neither side alone establishes equality. A search finding three paths has not ruled out a fourth, and finding a cut of size four has not proved that four routes exist.

A bridge is an edge whose deletion increases the number of connected components. In a connected graph, an edge is a bridge exactly when it lies on no cycle: a cycle provides an alternate route, and any alternate route would create a cycle with the edge. A cut vertex similarly disconnects a connected graph when removed. An architecture can have no bridge yet still possess a single cut vertex, as two cycles sharing one junction demonstrate. Edge redundancy and vertex redundancy are separate resources.

Global connectivity asks for the weakest separation anywhere in the graph, while the local question fixes endpoints. A region near two chosen servers may have several disjoint routes even though a remote leaf is attached by a bridge. Also, combinatorial disjointness models only the failures encoded by the graph. Two apparently separate links may share a conduit or power source. If that shared resource matters, it must appear in the model before a path theorem can justify a resilience claim.