Menger's Theorem
You'll learn: How Menger's theorem beautifully connects the number of disjoint paths between two vertices to the minimum separating set size in a graph.
The Core Idea
Menger's theorem answers a fundamental question: What's the maximum number of independent (disjoint) paths between two vertices, and how does that relate to connectivity?
Vertex Version: The maximum number of internally vertex-disjoint paths between two non-adjacent vertices u and v equals the minimum number of vertices whose removal disconnects u from v.
Edge Version: The maximum number of edge-disjoint paths between any two vertices u and v equals the minimum number of edges whose removal disconnects u from v.
Understanding Through Analogy
Think of a transportation network between two cities. Menger's theorem tells us that the maximum number of completely independent routes (sharing no intermediate cities in the vertex version, or no roads in the edge version) equals the smallest "bottleneck"—the minimum number of cities or roads you'd need to block to cut off all travel.
Why It Matters
This theorem directly explains vertex connectivity (κ(G)) and edge connectivity (λ(G)):
- κ(G) = minimum size of a separating vertex set = maximum internally disjoint paths between any pair
- λ(G) = minimum size of a separating edge set = maximum edge-disjoint paths between any pair
Menger's theorem proves these definitions are consistent and gives us a constructive way to find connectivity: look for disjoint paths rather than trying all possible cuts.
Key Takeaway: Menger's theorem establishes that the maximum number of disjoint paths between vertices equals the size of the minimum cut separating them—vertex-disjoint paths correspond to vertex cuts, edge-disjoint paths to edge cuts.