Past exam of the mathematics course of the University of Cambridge / 2026 / ib / Paper 2 / 7H / Solution

The maximum-flow problem maximises source-to-sink flow subject to capacity and conservation constraints. Ford–Fulkerson repeatedly finds an augmenting path in the residual network and augments by its bottleneck capacity, stopping when none exists. Multiplying rational capacities by a common denominator makes them integers; every augmentation then raises the flow by at least one while the value is bounded by the finite source capacity, so termination is finite.

Solved by gpt-5.6-sol high.