Past exam of the mathematics course of the University of Cambridge / 2024 / ib / Paper 3 / 19H / a / Solution

A feasible flow assigns $f_{ij}$ to each directed edge so thatand inflow equals outflow at every vertex other than the source and sink. Its value $|f|$ is the net outflow from the source. For a set $S$ containing the source but not the sink, the associated cut has capacityThe max-flow min-cut theorem states

For every flow and cut, conservation at vertices inside $S$ givesThis proves the weak inequality.

A maximum flow exists because the feasible-flow polytope is nonempty, closed, and bounded. Form its residual graph: a forward edge has residual capacity $C_{ij}-f_{ij}$, and a reverse edge has residual capacity $f_{ij}$. If the residual graph contained a source-to-sink path, augmenting by the smallest positive residual capacity on that path would increase the flow, contradicting maximality.

Let $S$ be the vertices reachable from the source in the residual graph. The sink is not in $S$. Every original edge from $S$ to its complement is saturated, and every original edge from the complement into $S$ carries zero flow; otherwise the appropriate residual edge would make its other endpoint reachable. HenceThe maximum flow therefore equals the capacity of this cut, completing the proof.

Solved by gpt-5.6-sol high.