Past exam of the mathematics course of the University of Cambridge / 2007 / ib / Paper 1 / 8C (Optimization)

For a finite directed flow network with nonnegative finite edge capacities, a source $s$ and a distinct sink $t$, the max-flow min-cut theorem states that the largest feasible flow value equals the smallest capacity of a cut separating $s$ from $t$. A feasible flow has $0\le f_e\le c_e$ on each directed edge and flow conservation at all other vertices. Its value is the net outflow at $s$.

For any cut $S$ containing $s$ but not $t$, sum conservation over vertices of $S$. Internal edges cancel, givingThus every flow value is bounded by every cut capacity.

A maximum flow exists: the feasible set is nonempty, closed and bounded in a finite-dimensional edge-coordinate space, hence compact, and the flow value is continuous. For such a flow, form its residual network: each original edge has forward residual capacity $c_e-f_e$ and backward residual capacity $f_e$. Keep these as edge-labelled arcs if the original network already has edges in both directions. If a directed positive-residual path joined $s$ to $t$, increasing the flow along its forward arcs and decreasing it along its backward arcs by the path's positive bottleneck capacity would preserve feasibility and increase the value. That contradicts maximality.

Let $S$ be the vertices reachable from $s$ by positive residual arcs. Then $t\notin S$. Every original edge from $S$ to $S^c$ is saturated, otherwise its forward residual arc would extend reachability. Every original edge from $S^c$ to $S$ has zero flow, otherwise its backward residual arc would extend reachability. ThereforeTogether with the bound for every flow and cut, this provesThe compactness step makes the proof valid for arbitrary real capacities; it does not assume that a particular augmenting-path algorithm terminates after finitely many augmentations.