Edge-Disjoint Paths and Menger's Theorem
What You'll Learn
You'll learn how network flow theory reveals the maximum number of edge-disjoint paths between two vertices and see how Menger's theorem elegantly connects path-counting to edge connectivity.
Edge-Disjoint Paths
Two paths in a graph are edge-disjoint if they share no common edges (though they may share vertices other than their endpoints). Finding the maximum number of edge-disjoint paths between vertices s and t is a fundamental graph problem with applications in network reliability and fault tolerance.
Think of it like finding independent routes from your house to work: edge-disjoint paths give you backup routes that don't share any roads, so if one road closes, your other routes remain intact.
Network Flow Connection
Here's the key insight: transform the graph into a network where every edge has capacity 1. The maximum flow from s to t equals the maximum number of edge-disjoint s-t paths! Why? Each unit of flow can be routed along a distinct path, and since edges have capacity 1, no edge appears in multiple paths.
Menger's Theorem (Edge Version)
Menger's Theorem states: The maximum number of edge-disjoint paths from s to t equals the minimum number of edges whose removal disconnects s from t (called a minimum s-t edge cut).
This is precisely the max-flow min-cut theorem in disguise! The min-cut represents the bottleneck—the smallest set of edges that, when removed, separates s and t. The theorem guarantees that you can find exactly that many independent paths.
Example: If removing any 3 edges always leaves s and t connected, but some set of 3 edges disconnects them, then there exist exactly 3 edge-disjoint s-t paths.
Key Takeaway: Menger's theorem unifies connectivity and paths: the maximum number of edge-disjoint paths between two vertices equals the size of the minimum edge cut separating them, directly applying max-flow min-cut theory.