The Max-Flow Min-Cut Theorem

The Max-Flow Min-Cut Theorem is the central result of flow networks. It states that the maximum value of a flow equals the minimum capacity of a cut separating $s$ from $t$, and it provides a constructive verification: when Ford-Fulkerson terminates, the set of vertices reachable from $s$ in the residual network is a minimum cut.

Cuts

An $(s, t)$-cut of a flow network is a partition of $V$ into sets $S$ and $T = V \setminus S$ such that $s \in S$ and $t \in T$.

The net flow across the cut is:

$f(S, T) = \sum_{u \in S} \sum_{v \in T} f(u, v) - \sum_{u \in S} \sum_{v \in T} f(v, u)$

The capacity of the cut (ignoring flow direction from $T$ to $S$) is:

$c(S, T) = \sum_{u \in S} \sum_{v \in T} c(u, v)$

Fundamental Lemma

For any flow $f$ and any cut $(S, T)$:

$|f| = f(S, T) \le c(S, T)$

Proof sketch: $|f| = f(S, T)$ follows from flow conservation (all flow from $s$ to $t$ must cross the cut, and internal vertices contribute zero net flow). $f(S, T) \le c(S, T)$ follows because each edge’s flow cannot exceed its capacity, and the second sum (from $T$ to $S$) is non-negative.

This immediately gives: $\max\text{-flow} \le \min\text{-cut}$.

The Theorem

Max-Flow Min-Cut Theorem: The following are equivalent:

1. $f$ is a maximum flow in $G$
2. The residual network $G_f$ contains no augmenting paths
3. $|f| = c(S, T)$ for some cut $(S, T)$ of $G$

Proof of Equivalence

(1) $\implies$ (2): If $G_f$ had an augmenting path $p$, augmenting along $p$ would yield a flow of value $|f| + c_f(p) > |f|$, contradicting maximality.

(2) $\implies$ (3): Since no path exists from $s$ to $t$ in $G_f$, define $S = \{v \in V \mid \text{there is a path from } s \text{ to } v \text{ in } G_f\}$ and $T = V \setminus S$. This is a cut ($s \in S$, $t \in T$). For any $u \in S, v \in T$:

• If $(u, v) \in E$, we must have $f(u, v) = c(u, v)$; otherwise $(u, v)$ would be in $E_f$, placing $v \in S$.
• If $(v, u) \in E$, we must have $f(v, u) = 0$; otherwise $(u, v) \in E_f$ with capacity $f(v, u) > 0$, again placing $v \in S$.

Hence $f(u, v) = c(u, v)$ for all forward edges and $f(v, u) = 0$ for all backward edges crossing the cut. Therefore $f(S, T) = c(S, T)$, so $|f| = c(S, T)$.

(3) $\implies$ (1): Since $|f| \le c(X, Y)$ for any cut $(X, Y)$, achieving equality means $f$ cannot be exceeded; it is maximum.

The proof is constructive: the cut $S$ obtained from the final residual network $G_f$ is a minimum cut.

Worked Example

Network (capacities on edges): $s \xrightarrow{10} a \xrightarrow{3} b \xrightarrow{7} t$, and $s \xrightarrow{5} b$, $a \xrightarrow{8} t$.

Maximum flow found: $|f| = 15$ (see Ford-Fulkerson Method).

Residual network at termination: $S = \{s, a\}$ (reachable from $s$ via residual edges), $T = \{b, t\}$.

Edges crossing $S \to T$:

• $a \to b$: capacity 3, $f(a, b) = 2$, residual capacity exists so not saturated? Wait: $c_f(a, b) = 1 > 0$, so $b$ should be reachable. Let us reanalyse.

In the final residual network after augmentations ($f(s,a)=10$, $f(a,t)=8$, $f(s,b)=5$, $f(a,b)=2$, $f(b,t)=7$):

• $(s,a)$ is saturated: $c_f(s,a)=0$, but $(a,s) \in E_f$ with capacity 10
• $(a,t)$ is saturated: $c_f(a,t)=0$, reverse $(t,a)$ capacity 8
• $(s,b)$ is saturated: $c_f(s,b)=0$, reverse $(b,s)$ capacity 5
• $(a,b)$: $c_f(a,b)=1$, reverse $(b,a)$ capacity 2
• $(b,t)$: saturated, reverse $(t,b)$ capacity 7

Reachable from $s$: $s$ itself, and following reverse edges: $(s,a)$ is in $E$, saturated forward, but there is no residual edge $s \to a$. However, is there a path $s \to a$ through some other route? No. So $S = \{s\}$.

Edges crossing $\{s\} \to \{a,b,t\}$: $s \to a$ (capacity 10, flow 10), $s \to b$ (capacity 5, flow 5). Cut capacity $= 10 + 5 = 15 = |f|$. Minimum cut found.

Summary

Statement	Meaning
Cut $(S, T)$	Partition with $s \in S$, $t \in T$
$f(S, T)$	Net flow across cut; equals $\lvert f \rvert$
$c(S, T)$	Sum of forward capacities across cut
$\lvert f \rvert \le c(S, T)$	Weak duality — always true
$\max\text{-flow} = \min\text{-cut}$	Strong duality — the theorem
$S$ from $G_f$	Vertices reachable from $s$ in residual network — a min cut

Past Tripos: y2024p2q7, y2023p1q9.