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

Edge-Disjoint Paths and Menger's Theorem

Apply network flow theory to find edge-disjoint paths and state Menger's theorem on connectivity.

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.