Menger's Theorem and Network Connectivity

Menger's theorem links the maximum number of disjoint paths between two vertices to the minimum number of edges or vertices whose removal separates them. This lesson develops both the edge and vertex versions of Menger's theorem as direct consequences of max-flow min-cut, then introduces the global connectivity parameters $\lambda(G)$ and $\kappa(G)$ together with the chain $\kappa(G) \le \lambda(G) \le \delta(G)$ .

Step 1 of 157%

Tutorial

Edge-Disjoint Paths and Menger's Theorem

In a graph $G$ with two distinguished vertices $s$ and $t$ , we often want to count alternative routes between them.

Two $s$ - $t$ paths are edge-disjoint if they share no edges. They may still share internal vertices.

The edge connectivity from $s$ to $t$ , denoted $\lambda(s,t)$ , is the minimum number of edges whose removal disconnects $t$ from $s$ .

Menger's Theorem (Edge Version). In any graph, the maximum number of pairwise edge-disjoint $s$ - $t$ paths equals $\lambda(s,t)\!:$

\max\{\text{edge-disjoint } s\text{-}t \text{ paths}\} \;=\; \lambda(s,t).

This is the max-flow min-cut theorem applied to $G$ with every edge given unit capacity. Each edge-disjoint path carries one unit of flow, so the max flow counts the paths; a minimum edge cut is then a minimum capacity cut.

For instance, consider the graph on vertices $\{s, a, b, t\}$ with edges

\{s,a\},\;\{s,b\},\;\{a,t\},\;\{b,t\}.

The paths $s\text{-}a\text{-}t$ and $s\text{-}b\text{-}t$ are edge-disjoint, and removing the two edges $\{s,a\}$ and $\{s,b\}$ isolates $s$ . So $\lambda(s,t) = 2$ , matching the two paths.