 Solution

Take a finite directed flow network with distinct source $s$, sink $t$ and finite nonnegative flow network edge capacities. A flow assigns $f_e$ to each edge with $0\le f_e\le c_e$ and obeys flow conservation at every vertex except $s,t$. Its value is net outflow from the source, $|f|={\sum }_{s\to v}{f}_e-{\sum }_{v\to s}{f}_e$. A maximal flow here means a maximum flow: one with greatest value among feasible flows. A source-to-sink cut of a flow network is a partition $(S,S^c)$ with $s\in S$, $t\notin S$; its cut capacity is $c(S)={\sum }_{u\in S,v\notin S}{c}_{uv}$, counting directed edges leaving $S$.

The max-flow min-cut theorem statesSumming conservation over $S$ cancels internal edges and givesThis is the upper bound for every flow and every cut. To prove equality, a maximum exists: the feasible edge vectors form a nonempty closed bounded subset of a finite-dimensional real space, and flow value is continuous.

For a maximum $f$, construct its residual network. Each edge has a forward residual edge of capacity $c_e-f_e$ and a backward residual edge of capacity $f_e$; retain those of positive capacity. If a residual source-to-sink path existed, augment by the smallest residual capacity on that finite path. Increasing original forward flows and decreasing backward flows preserves all feasibility conditions and increases value, contradicting maximality. Thus no such augmenting path exists.

Let $S$ be the vertices reachable from $s$ in the residual network. Then $t\notin S$. Every original edge leaving $S$ is saturated, since otherwise its positive forward residual edge would make its endpoint reachable. Every original edge entering $S$ has zero flow, since otherwise its backward residual edge would give the same contradiction. HenceTogether with the universal upper bound this proves equality and identifies a minimum cut. This proof covers real capacities without assuming that an augmenting-path algorithm terminates after finitely many steps. Merely being impossible to increase all edge flows coordinatewise is not the optimization meaning of “maximal” used in the theorem.