= Solution
Assume the capacities are integers and begin with the zero flow. Inductively, if every edge flow is an integer, then every forward residual capacity $c(u,v)-f(u,v)$ and reverse residual capacity $f(u,v)$ is an integer. The bottleneck on an <augmenting path> is therefore a positive integer. Augmenting by it changes every affected edge flow by an integer, so all edge flows remain integral.
Each augmentation raises the flow value by at least one. On the other hand, every feasible flow satisfies
$$
|f|\leq\sum_{v}c(S,v),
$$
and the right side is a finite integer because the network is finite. There can therefore be only finitely many augmentations. When the algorithm stops, no augmenting path remains, and the source-reachable cut in the residual network has capacity equal to the current flow value. The <max-flow min-cut theorem> proves that the terminating flow is maximum. This proves both termination and the <Integrality of the Ford-Fulkerson algorithm>.
Back to article page
