Graph Theory
The Max-Flow Min-Cut Theorem
Cut a pipeline network at its narrowest point and you have found its true capacity — no amount of clever routing can push more water than the tightest bottleneck allows. The Max-Flow Min-Cut Theorem makes this intuition exact: in any finite network with a source s and sink t and nonnegative edge capacities, the maximum value of an s–t flow equals the minimum capacity of an s–t cut. Two problems that look nothing alike — a maximization over all flows and a minimization over all ways to sever the graph — have precisely the same answer.
Proved independently by Lester Ford and Delbert Fulkerson, and by Peter Elias, Amiel Feinstein, and Claude Shannon, all in 1956, it is the combinatorial heart of linear programming duality and the ancestor of a dozen classical results, from König's theorem to Menger's theorem.
- FieldCombinatorial optimization / graph theory
- First proved1956 (Ford–Fulkerson; Elias–Feinstein–Shannon)
- Statementmax value of s–t flow = min capacity of s–t cut
- Key hypothesisFinite network, nonnegative capacities, single source/sink
- Proof techniqueAugmenting paths in the residual graph (LP strong duality)
- GeneralizesMenger's theorem, König's theorem, Hall's marriage theorem
Interactive visualization
Press play, or step through manually. The visualization is yours to drive — try it before reading on.
Watch the 60-second explainer
A condensed visual walkthrough — narrated, captioned, under a minute.
The precise statement
Let N = (V, E) be a finite directed graph with a distinguished source s and sink t, and a capacity function c: E → ℝ≥0. A flow is a function f: E → ℝ satisfying two constraints:
- Capacity: 0 ≤ f(e) ≤ c(e) for every edge e.
- Conservation: for every vertex v ∉ {s, t}, flow in = flow out, i.e. ∑ᵤ f(u,v) = ∑ᵥ f(v,w).
The value |f| is the net flow out of s. An s–t cut is a partition (S, T) of V with s ∈ S, t ∈ T; its capacity is c(S,T) = ∑ over edges from S to T of c(e) (edges from T to S contribute nothing). The theorem states:
max over all flows |f| = min over all s–t cuts c(S,T).
The picture: bottlenecks and certificates
Imagine water pipes from a reservoir s to a city t. However you distribute flow through the interior, every drop that reaches t must at some point cross from the s-side of any partition to the t-side. So the total flow can never exceed the combined capacity of the pipes crossing that partition. This is weak duality: |f| ≤ c(S,T) for every flow and every cut — one direction, and it is almost trivial.
The content of the theorem is that this bound is tight: there is always some cut whose capacity is achieved exactly, and some flow saturating it. The minimum cut is the genuine bottleneck. Better still, a min cut is a certificate: if someone hands you a flow of value v and a cut of capacity v, you instantly know both are optimal — no further search required. This certificate structure is exactly what makes flow algorithms verifiable and is the combinatorial shadow of LP duality.
Key idea of the proof: augmenting paths and the residual graph
The engine is the residual graph G_f. Given a flow f, each edge (u,v) with slack contributes a forward residual edge of capacity c(e) − f(e); each edge carrying flow contributes a backward residual edge of capacity f(e), which lets us cancel flow. An augmenting path is any directed s→t path in G_f; pushing flow equal to its bottleneck residual capacity strictly increases |f|.
The crux is the termination condition. When no augmenting path exists, let S = { vertices reachable from s in G_f }, and T = V ∖ S. Since t ∉ S, this is a valid cut. Every edge from S to T must be saturated (else its forward residual would extend S), and every edge from T to S must carry zero flow (else a backward residual would reach into T). Summing, |f| = c(S,T). Combined with weak duality, this forces both to be optimal. The construction produces the min cut for free.
A worked example
Take four vertices s, a, b, t with capacities: s→a = 3, s→b = 2, a→b = 1, a→t = 2, b→t = 3.
- Push 2 along s→a→t. Push 2 along s→b→t. Now |f| = 4. Edge a→t is saturated (2/2), s→b saturated (2/2).
- Seek another augmenting path. From s: only s→a has slack (2 used of 3). From a: a→t is full, but a→b has capacity 1, then b→t has slack (2 used of 3). Push 1 along s→a→b→t.
- Now |f| = 5. No augmenting path remains. After this final augmentation s→a (3/3) and s→b (2/2) are both saturated, so the residual-reachable set is S = {s}.
The cut ({s}, {a,b,t}) crosses edges s→a (3), s→b (2), total 5 = |f|. Maximum flow equals minimum cut, exactly as promised. (The cut ({s,a}, {b,t}) is also a minimum cut of value 5, but it is not the one the residual-reachability construction produces.)
Why the hypotheses matter
Finiteness / rational capacities. The augmenting-path argument terminates immediately when capacities are integers or rationals (each augmentation adds at least a fixed amount). With irrational capacities and a bad choice of paths, Ford–Fulkerson can loop forever, the flow value converging to a number below the true maximum — a genuine counterexample (Ford & Fulkerson's own construction; also Zwick's). The fix is choosing augmenting paths well: Edmonds–Karp (shortest paths, BFS) always terminates in O(VE²), independent of capacities. The theorem itself still holds for real capacities via LP compactness, but the naive algorithm need not.
Single source and sink. Multiple sources/sinks reduce to the single case by a super-source and super-sink. Nonnegative capacities are essential; negative bounds change the problem. The theorem is the combinatorial core of strong LP duality, and it directly generalizes Menger's theorem (edge-disjoint paths = min edge cut), König's theorem (max matching = min vertex cover in bipartite graphs), and Hall's marriage theorem.
Applications and significance
Max-flow min-cut is one of the most-applied theorems in all of computer science and operations research. A partial roster:
- Bipartite matching: unit-capacity flow computes maximum matchings; the min cut yields König's minimum vertex cover.
- Image segmentation: the graph cut method in computer vision finds an optimal foreground/background partition as a minimum s–t cut of a pixel grid.
- Network reliability & connectivity: Menger's theorem, computed by flows, gives the number of edge-disjoint or vertex-disjoint paths — a direct measure of fault tolerance.
- Project selection, baseball elimination, scheduling: classic combinatorial problems that reduce to a min cut.
- Integrality: when capacities are integers, an integer maximum flow exists — the source of many exact combinatorial guarantees.
Its true significance is conceptual: it is the clearest, most concrete instance of duality — a maximization and a minimization pinned to the same value, each certifying the other's optimality. Learn it and every later duality (LP, semidefinite, minimax) has a picture to anchor it.
| Quantity | Definition | Relationship |
|---|---|---|
| Value of a flow |f| | Net flow leaving the source s = ∑ out of s − ∑ into s | Every feasible flow ≤ every cut capacity (weak duality) |
| Capacity of a cut c(S,T) | ∑ of capacities of edges from S to T, where s∈S, t∈T | Upper-bounds every flow; gives certificate of optimality |
| Maximum flow (max |f|) | Largest achievable |f| over all feasible flows | EQUAL to minimum cut (strong duality — the theorem) |
| Minimum cut (min c(S,T)) | Smallest cut capacity over all s–t partitions (S,T) | EQUAL to maximum flow; achieved by residual reachable set |
| Integrality | If all capacities are integers, max flow is integral | Integral optimum exists (integrality theorem) |
Frequently asked questions
What is the difference between weak and strong duality here?
Weak duality is the easy half: every feasible flow value is at most every cut capacity, |f| ≤ c(S,T), because all flow must cross any cut. Strong duality is the theorem itself — that the maximum flow exactly equals the minimum cut, with no gap. The augmenting-path proof establishes strong duality by exhibiting a flow and a cut of equal value.
Why can the Ford–Fulkerson algorithm fail to terminate?
With irrational capacities and a pathological choice of augmenting paths, the amount pushed each iteration can shrink geometrically, so the flow value converges to a limit strictly below the true maximum without ever reaching it. This is a real counterexample. Choosing paths by BFS (Edmonds–Karp) or by widest-bottleneck fixes it and gives a polynomial bound; the theorem remains true regardless.
Does the theorem still hold with real-valued (irrational) capacities?
Yes. The equality max flow = min cut holds for any nonnegative real capacities — it is a consequence of LP strong duality and compactness of the feasible flow polytope. Only the naive augmenting-path algorithm can misbehave on irrational data; the mathematical statement is unaffected.
What is the integrality theorem and why is it useful?
If every capacity is an integer, then there exists a maximum flow in which every edge carries an integer amount. This follows because augmenting paths push integer bottleneck values when capacities are integers. It is the reason flow reductions solve combinatorial problems exactly — matchings, disjoint paths, and assignments come out as 0/1 (integral) solutions.
How does this relate to Menger's theorem and König's theorem?
Both are special cases. Menger's theorem (the maximum number of edge-disjoint s–t paths equals the minimum s–t edge cut) is max-flow min-cut with all capacities 1. König's theorem (in a bipartite graph, max matching size = min vertex cover size) follows by building a unit-capacity flow network with a super-source and super-sink and reading off the min cut.
Is the minimum cut unique?
Not in general — a network can have several distinct minimum cuts of the same capacity. However, the augmenting-path proof canonically produces one specific min cut: S = the set of vertices reachable from s in the final residual graph. There is also a unique minimal (closest to s) and a unique maximal min cut, and all min cuts form a lattice.