Augment to the Max - Max-Flow, Min-Cut

Ford-Fulkerson repeats a simple improvement loop: find a residual source-to-sink route, push its bottleneck, and rebuild the residual graph. With integer capacities, each augmentation increases the flow by an integer amount, so the sequence cannot make endlessly tiny improvements on this instance. This lesson reads the final flow value after the deterministic sequence ends.

highlighted = computed this step

Repeat augmenting

The deterministic search uses 3 augmenting paths. Each path is found in the current residual graph, then pushed by its bottleneck. Why: with integer capacities, every bottleneck is an exact positive integer, so each accepted path makes visible progress.

\text{augment until no path remains}

Last push

The last augmenting path adds 1 unit. This final push saturates the remaining route that mattered for increasing the total flow. Why: after that push, the residual graph has no source-to-sink route left, so there is no legal way to add more.

\Delta_{\text{last}}=1

Max flow value

The resulting maximum flow value is 4. This is not accepted merely because the algorithm stopped; it is accepted because the residual graph supplies no augmenting path. Why: any larger feasible flow would imply some residual way to push more from source to sink.

|f^*|=4

Diagram note

Every flow over capacity label is recomputed by the exact integer max-flow routine. The diagram shows the terminal flow state; the optimality proof will come from matching it to a cut. Pixel positions are rounded for layout; every number shown is exact.

\text{no residual path means the flow is maximal}