= Solution
{c}
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 \b[integer capacities guarantee an integer optimal volume], even though arbitrary feasible real-valued flows need not themselves have integer entries.
Back to article page
