Min-Cut and Max-Flow Duality
What You'll Learn
You'll discover the fundamental relationship between finding the maximum flow and finding the minimum cut in a network—and why they're always equal.
The Core Idea
Imagine a network of pipes carrying water from a source to a sink. The max-flow min-cut theorem states two remarkable facts are always identical:
- Maximum Flow: The most water you can push from source to sink
- Minimum Cut: The smallest total capacity of edges you'd need to remove to completely disconnect the source from the sink
This isn't coincidence—it's a deep duality. The maximum flow is limited by the minimum cut. Think of it like this: if you remove the bottleneck edges (the min-cut), no flow can get through at all. Conversely, you can always achieve a flow equal to that cut's capacity.
Why This Matters
A cut partitions the network into two sets: nodes reachable from the source (S) and nodes on the sink's side (T). The cut's capacity is the sum of all edge capacities going from S to T.
The min-cut identifies the exact bottleneck in your network—the weakest link limiting flow. For example:
- In transportation: which roads, if closed, would halt traffic most efficiently
- In network security: which connections are critical vulnerabilities
- In project scheduling: which tasks are the critical constraints
Once you've computed max-flow (using Ford-Fulkerson, Edmonds-Karp, or Dinic's), you automatically know the min-cut value—it equals the max-flow! The actual bottleneck edges are those saturated edges crossing from nodes reachable in the residual network to those that aren't.
Key Takeaway: The max-flow min-cut theorem proves that the maximum flow value always equals the minimum cut capacity, revealing the network's fundamental bottleneck and enabling powerful optimization applications.