Past exam of the probability, statistics and options I course of the University of Oxford / 2007 / S / 2 / b

Start the augmenting-path algorithm from the zero flow. With integer capacities and an integer electric current flow, every residual capacity is an integer, so a path bottleneck is a positive integer. Augmenting by it preserves integrality and increases the flow value by at least one. The value is bounded by the finite total capacity leaving the source, so the process terminates. At termination there is no augmenting path, hence the flow is maximum by the max-flow min-cut theorem. Its value is an integer.

Equivalently a minimum cut has capacity equal to the sum of integer arc capacities, so the maximum flow value equals an integer. Thus integer capacities guarantee an integer optimal volume, even though arbitrary feasible real-valued flows need not themselves have integer entries.