Max-Flow Min-Cut Theorem

A flow network is a directed graph $G = (V, E)$ with a nonnegative capacity $c(u,v) \ge 0$ on each edge, a source $s$, and a sink $t$ (assume no edges enter $s$ or leave $t$, without loss of generality). A flow is a function $f : V \times V \to \mathbb{R}$ satisfying capacity constraints ($0 \le f(u,v) \le c(u,v)$) and flow conservation (inflow equals outflow at every vertex except $s$ and $t$). The value of a flow is the net flow leaving the source, $|f| = \sum_v f(s,v) - \sum_v f(v,s)$. An s-t cut is a partition of $V$ into two sets $S$ and $T = V \setminus S$ with $s \in S$ and $t \in T$. The capacity of the cut is

summing capacities only in the direction from $S$ to $T$ — edges from $T$ back into $S$ do not count, even though they exist in the graph. This asymmetry is essential: a cut is meant to bound flow that must cross the boundary going "forward," and reverse-direction capacity does nothing to prevent that. The central claim connecting these two objects has two halves. Weak duality says every flow value is at most every cut capacity — this direction is a simple accounting argument and holds unconditionally. Strong duality, the Max-Flow Min-Cut Theorem proper, says that equality is always attainable: there exists some flow and some cut whose numbers coincide, and that common value is simultaneously the maximum flow and the minimum cut. The proof of strong duality is where the real content lives, and it comes packaged with a residual graph — the same structure used to run Ford-Fulkerson Method — which supplies both the augmenting-path termination condition and the minimum cut itself, in one stroke.

Weak duality, precisely

Claim. For any flow $f$ and any s-t cut $(S,T)$, $|f| \le c(S,T)$.

Argument. By conservation, the flow value equals the net flow crossing the cut in either direction:

This holds because summing conservation at every vertex in $S$ telescopes internal-to-$S$ terms to zero, leaving exactly the boundary terms (a standard "flow across a cut" identity). Each term $f(u,v) \le c(u,v)$, and each subtracted term is nonnegative, so

This holds for every flow and every cut, immediately giving: $\max_f |f| \le \min_{(S,T)} c(S,T)$. The theorem's content is that this inequality is actually equality.

The residual graph and augmenting paths

For a flow $f$, the residual graph $G_f$ has, for each edge $(u,v) \in E$, a forward residual edge with capacity $c_f(u,v) = c(u,v) - f(u,v)$ (if positive), and a backward residual edge $(v,u)$ with capacity $c_f(v,u) = f(u,v)$ (if positive) representing the ability to cancel existing flow. An augmenting path is any $s \to t$ path in $G_f$ using only positive-residual-capacity edges; pushing flow equal to the path's bottleneck capacity along it strictly increases $|f|$.

The three-way characterization

Theorem. Let $f$ be a flow in network $G$. The following are equivalent: 1. $f$ is a maximum flow in $G$. 2. The residual graph $G_f$ contains no augmenting path from $s$ to $t$. 3. $|f| = c(S,T)$ for some s-t cut $(S,T)$.

Proof sketch. (1) $\Rightarrow$ (2). If an augmenting path existed, we could push additional flow along it and strictly increase $|f|$, contradicting maximality. (2) $\Rightarrow$ (3). Suppose $G_f$ has no augmenting path. Let $S$ be the set of vertices reachable from $s$ in $G_f$, and $T = V \setminus S$. Since there is no path to $t$, $t \in T$, so $(S,T)$ is a valid s-t cut. Now examine any edge $(u,v)$ with $u \in S$, $v \in T$: since $v$ is unreachable from $s$ but $u$ is reachable, the residual edge $(u,v)$ cannot exist in $G_f$ (else $v$ would be reachable too) — so $c_f(u,v) = 0$, meaning $f(u,v) = c(u,v)$ (the forward edge is saturated). Symmetrically, for any edge $(v,u)$ with $v \in T, u \in S$, the residual backward edge $(u,v)$ cannot exist either, forcing $f(v,u) = 0$ (no flow enters $S$ from $T$). Plugging both facts into the flow-across-a-cut identity:

(3) $\Rightarrow$ (1). By weak duality, $|f| \le c(S,T)$ for every cut, in particular this one, so $|f| \le c(S,T)$. But we're given $|f| = c(S,T)$ exactly, and every other flow $f'$ satisfies $|f'| \le c(S,T) = |f|$. Hence $f$ is maximum. $\blacksquare$ Chaining these three implications closes the cycle $(1) \Rightarrow (2) \Rightarrow (3) \Rightarrow (1)$, proving all three equivalent — and, as a byproduct, proving strong duality: the maximum flow value equals the capacity of the specific cut constructed in step (2), which must therefore be a minimum cut (any smaller cut would violate weak duality against this flow).

Algorithm: extracting flow and cut together

``` FORD-FULKERSON-WITH-CUT(G, s, t, c): for each edge (u, v) in G: f(u, v) <- 0 build residual graph G_f from f and c while there exists a path P from s to t in G_f (using edges with positive residual capacity): b <- min residual capacity along P // bottleneck for each edge (u, v) in P: if (u, v) is a forward edge in G: f(u, v) <- f(u, v) + b else // (u,v) is a backward residual edge, f(v, u) <- f(v, u) - b // meaning true edge is (v,u) update G_f accordingly // No augmenting path remains: extract the minimum cut for free S <- { v in V : v is reachable from s in G_f } // via BFS/DFS T <- V \ S return f, (S, T) ``` The loop is exactly Ford-Fulkerson; the only addition is the final reachability pass, which is what the proof of $(2) \Rightarrow (3)$ constructs explicitly. Running BFS instead of arbitrary path search gives Edmonds–Karp, with the same cut-extraction step appended unchanged.

Correctness is exactly the three-way equivalence proved above: the algorithm halts precisely when no augmenting path exists, at which point condition (2) holds, forcing conditions (1) and (3) — the current flow is simultaneously maximum, and the reachable-set partition is simultaneously a minimum cut. No separate correctness argument is needed for "why does the cut we output actually have minimum capacity" — it falls out of the same reachability computation used to detect termination. This is the theorem's real payoff: optimality is self-certifying, not something requiring an external check against all other cuts.

Time complexity depends on the augmenting-path strategy layered on top of this framework, since the theorem itself is strategy-agnostic:

• Generic Ford-Fulkerson (arbitrary augmenting path, integer capacities): each augmentation increases $|f|$ by at least $1$, so the loop runs at most $|f^*|$ times (the max-flow value), each augmentation costing $O(E)$ to find a path via BFS/DFS and $O(V)$ to update it — total $O(E \cdot |f^*|)$. This is pseudo-polynomial: with capacities in the billions, $|f^*|$ can be astronomically larger than $V$ or $E$, and a poorly chosen sequence of paths can genuinely realize this slowdown.
• Edmonds–Karp (always augment along a shortest path, by edge count, found via BFS): guarantees $O(VE)$ augmentations, each costing $O(E)$, for $O(VE^2)$ total — genuinely polynomial, independent of capacity magnitudes.
• The final cut-extraction step (one BFS/DFS over $G_f$) costs $O(V+E)$ and is performed once, so it never dominates the asymptotic bound.

Space complexity is $O(V + E)$: the residual graph mirrors the original graph's structure with at most a constant-factor blowup (one reverse edge per original edge), and the flow values themselves are stored per edge.

Honest tradeoffs. The theorem guarantees the existence of a matching flow/cut pair and gives a clean stopping condition, but says nothing about how fast you reach that state — that is entirely the job of the augmenting-path selection rule. The theorem also assumes finite capacities (or requires care with infinite-capacity edges) and, in its basic form, real- or integer-valued capacities; with irrational capacities and poorly chosen augmenting paths, Ford-Fulkerson can in principle fail to converge at all, though this pathology does not arise under Edmonds–Karp or with integer capacities. Finally, the minimum cut produced is a minimum cut — networks can have multiple cuts of equal minimum capacity, and the algorithm returns whichever one corresponds to the specific terminal residual graph reached.

Consider a small network: source $s$, sink $t$, and intermediate vertices $a, b$. Edges and capacities: $s\!\to\!a: 3$, $s\!\to\!b: 2$, $a\!\to\!b: 1$, $a\!\to\!t: 2$, $b\!\to\!t: 3$.

At termination, run BFS from $s$ in $G_f$. Remaining forward residual edges: none out of $s$ (both $s\!\to\!a$ and $s\!\to\!b$ are saturated, residual $0$); the only edges out of $s$ in $G_f$ would be backward edges into $s$, which don't count as outgoing. So $S = \{s\}$ exactly — no vertex is reachable — and $T = \{a, b, t\}$. Compute the cut capacity $c(S,T)$: sum capacities of edges from $S=\{s\}$ to $T$. These are $s\!\to\!a$ (capacity 3) and $s\!\to\!b$ (capacity 2), giving

This matches $|f| = 5$ exactly, confirming via condition (3) that $f$ is maximum and $(S,T)$ is a minimum cut — no further search over other partitions is needed. Notice this is not the visually "obvious" bottleneck (one might have guessed the $a\!\to\!b$ edge, capacity $1$, matters more than it does); the theorem's certificate removes any doubt about which cut is truly binding.

The theorem emerged from RAND Corporation research into Cold War-era logistics and transportation-network planning, where the practical question was literally about rail and pipeline capacities under adversarial interdiction.

Network reliability engineers use min-cut computations to find the cheapest set of links whose failure would partition a communication or power network — directly reporting the min-cut capacity as the "weakest link" bandwidth of the whole system. Compiler and hardware design tools use flow-based min-cut algorithms for register allocation and circuit partitioning, where the cut corresponds to wires or variables that must cross a physical or logical boundary. Computer vision systems use min-cut/max-flow formulations for image segmentation, treating pixel similarity as edge capacity and separating foreground from background via a minimum boundary cut. Airline and logistics scheduling systems model crew and aircraft assignment as flow problems, where max-flow answers "can this schedule be covered" and min-cut identifies the exact bottleneck resource. Most directly, the theorem is the correctness backbone for Bipartite Matching via Augmenting Paths: casting bipartite matching as a unit-capacity flow problem, the max-flow min-cut equivalence guarantees that the maximum matching size equals the flow value found by augmenting paths, with König's theorem on minimum vertex covers falling out as a direct corollary of the minimum cut structure.

Ask the tutor: How does the choice of augmenting path (arbitrary vs. shortest vs. max-bottleneck) affect which minimum cut the algorithm ultimately reports?