= Solution
For a finite directed <flow network> with source $s$, sink $t$ and nonnegative finite <flow network edge capacities> $c_e$, the <max-flow min-cut theorem> states
$$
\boxed{\max_{f\text{ feasible}}|f|=\min_{S:s\in S,\ t\notin S}c(S,S^c).}
$$
Here feasible arc flows satisfy $0\leq f_e\leq c_e$ and <flow conservation> at every vertex except $s,t$. Their <strength of a flow> is the net outflow at $s$. A <cut of a flow network> has <cut capacity> equal to the sum of capacities on arcs directed from $S$ to $S^c$.
For any feasible <flow> and any such <cut of a flow network>, summing <flow conservation> over $S$ cancels internal arcs and gives
$$
|f|=\sum_{u\in S,v\notin S}f_{uv}-\sum_{u\notin S,v\in S}f_{uv}\leq\sum_{u\in S,v\notin S}c_{uv}=c(S,S^c).
$$
Thus every flow value is bounded by every cut capacity.
A maximum <flow> exists: the feasible arc-flow vectors form a nonempty closed subset of the finite-dimensional compact box $\prod_e[0,c_e]$, and flow value is continuous. Choose one, $f^*$. Its <residual network> has a forward arc of capacity $c_e-f_e^*$ and a reverse arc of capacity $f_e^*$ for each original arc. If a residual $s$–$t$ <augmenting path> existed, its smallest positive residual capacity would permit increasing forward flows and decreasing reverse flows along the path. This preserves all capacity bounds and internal <flow conservation> while strictly increasing $|f^*|$, a contradiction.
Let $S$ be the vertices reachable from $s$ through positive residual arcs. Then $t\notin S$. Every original arc leaving $S$ is saturated, since otherwise its endpoint would also be reachable. Every original arc entering $S$ carries zero flow, since a positive flow would create a residual reverse arc leaving $S$. Therefore
$$
|f^*|=\sum_{u\in S,v\notin S}c_{uv}=c(S,S^c).
$$
Together with the universal upper bound, this proves both optimality claims and the theorem. This existence argument works for real capacities; it does not assume that arbitrary choices in the <Ford-Fulkerson algorithm> terminate. For integer capacities, positive augmentations are integral and increase the flow value by at least one, so the algorithm does terminate.
Back to article page
