Course contentsShow
← Mathematics
Lesson 2666 of 3,12153. Graph TheoryFree lesson

Menger's Theorem

State and apply Menger's theorem relating disjoint paths to connectivity; understand vertex and edge versions.

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.