Why Integrality Matters
In a capacity-constrained network, capacities may represent indivisible quantities: vehicles, packets, or units of a product. If all capacities are integers, it is natural to ask whether a maximum flow can also be chosen with integer values on every arc. Ford–Fulkerson answers this constructively: starting from an integer feasible flow, every augmentation remains integer. Moreover, when capacities are integers, the procedure cannot augment forever.
The starting-flow hypothesis is essential to this argument. Integer capacities ensure integer residual capacities only when the current flow is integer. We will prove that the bottleneck of each augmenting path is then a positive integer, that each update preserves integrality, and that a simple bound on flow value forces termination.
Networks, Residual Arcs, and Augmentation
Arcs in opposite directions are treated as distinct original arcs. For an original arc \(a=(u,v)\), its forward residual arc goes from \(u\) to \(v\) and has residual capacity \(c(a)-f(a)\); its reverse residual arc goes from \(v\) to \(u\) and has residual capacity \(f(a)\). The reverse residual arc records the option of cancelling some flow on \(a\). If the network already contains an original arc in the reverse direction, its residual arcs are still distinguished by which original arc they come from.
Here and below, an augmenting path has no repeated vertices. The standard flow-augmentation result says that augmenting a feasible flow by an amount no greater than the bottleneck produces another feasible flow and increases its value by that amount. The reason is that every updated original-arc flow stays between zero and its capacity, each internal path vertex gains and loses the same amount of flow, and the source’s net outflow rises by the update amount.
Proof. On a forward residual arc for \(a\), the residual capacity is \(c(a)-f(a)\), a difference of integers. On a reverse residual arc for \(a\), it is \(f(a)\), also an integer. Along an augmenting path every residual capacity is positive, so each is a positive integer. The path has finitely many arcs, and its bottleneck is the minimum of their positive integer residual capacities; that minimum is a positive integer. \(\square\)
The Integrality and Termination Theorem
Proof. We first establish integrality at every iteration. The initial flow is integral by hypothesis. Suppose the current flow is integral. The Lemma gives an integer bottleneck on every chosen augmenting path. The flow update adds or subtracts this integer on each affected original arc and leaves all other arc flows unchanged. Thus the updated flow remains integral. It remains feasible by the flow-augmentation result. Induction on the number of augmentations proves that every flow produced is feasible and integral.
For termination, let \(C\) be the sum of the capacities of all original arcs leaving \(s\). For any feasible flow \(f\), its value is the total flow on arcs leaving \(s\) minus the total flow on arcs entering \(s\). Flow on entering arcs is nonnegative, and flow on each leaving arc is at most its capacity. Therefore \(|f|\le C\). This argument also applies when there are no arcs leaving \(s\), in which case \(C=0\).
At each augmentation, the value increases by the bottleneck, which is a positive integer by the Lemma and the integrality induction. Hence it increases by at least \(1\). Write \(F_0\) for the initial flow value and \(F_k\) for the value after \(k\) augmentations. If \(k\) augmentations have occurred, then \(F_k\ge F_0+k\), while feasibility gives \(F_k\le C\). Thus \(k\le C-F_0\). The initial flow is feasible, so \(F_0\le C\); since \(C\) and \(F_0\) are integers, this is a finite nonnegative integer bound on the number of augmentations. The algorithm must therefore stop.
At termination there is no augmenting path. The augmenting path characterization, established in the earlier material on augmenting paths, states that for a feasible flow in a finite network, the flow is maximum if and only if no residual \(s\)-\(t\) path exists. Its hypotheses hold here: the network is finite and the terminal flow is feasible. The terminal flow is therefore maximum, and the integrality induction shows that it is integral. \(\square\)
The algorithm may choose any available augmenting path; the proof does not require a particular path-selection rule. The integer bound guarantees termination, but it is not a claim that the number of augmentations is small. Efficiency depends on how paths are selected, a separate issue from integrality.
Worked Augmentations
Worked Example: Three Integer Bottlenecks
Let the directed network have vertices \(V=\{s,a,b,t\}\) and arcs \(s\to a\) of capacity \(3\), \(s\to b\) of capacity \(2\), \(a\to t\) of capacity \(2\), \(b\to t\) of capacity \(3\), and \(a\to b\) of capacity \(1\). Start with zero flow. Choose the paths shown below; the listed residual capacities are evaluated just before each augmentation.
| Step | Augmenting path | Residual capacities on path | Bottleneck | Flow value after update |
|---|---|---|---|---|
| 1 | \(s\to a\to t\) | \(3,2\) | \(\min(3,2)=2\) | \(0+2=2\) |
| 2 | \(s\to b\to t\) | \(2,3\) | \(\min(2,3)=2\) | \(2+2=4\) |
| 3 | \(s\to a\to b\to t\) | \(1,1,1\) | \(\min(1,1,1)=1\) | \(4+1=5\) |
The final arc flows are \(f(s\to a)=3\), \(f(s\to b)=2\), \(f(a\to t)=2\), \(f(b\to t)=3\), and \(f(a\to b)=1\). Conservation holds at \(a\), since its inflow is \(3\) and its outflow is \(2+1=3\); it holds at \(b\), since its inflow is \(2+1=3\) and its outflow is \(3\). The source’s net outflow is \(3+2=5\). Both arcs leaving \(s\) are saturated, so there is no residual arc leaving \(s\), and hence no augmenting path. By the augmenting path characterization, this integral flow is maximum.
Worked Example: An Integer Update Using a Reverse Arc
Let \(V=\{s,a,b,t\}\), with arcs \(s\to a\), \(s\to b\), \(a\to b\), \(a\to t\), and \(b\to t\), each of capacity \(1\). Begin with the feasible integer flow \(f(s\to a)=1\), \(f(s\to b)=0\), \(f(a\to b)=1\), \(f(a\to t)=0\), \(f(b\to t)=1\). At \(a\), inflow and outflow are both \(1\); at \(b\), inflow and outflow are both \(1\); the flow value is \(1\).
There is a residual path \(s\to b\to a\to t\). The middle residual arc is the reverse of the original arc \(a\to b\). The residual capacities along the path are \(1\) on \(s\to b\), \(1\) on the reverse of \(a\to b\), and \(1\) on \(a\to t\). Thus the bottleneck is \(\min(1,1,1)=1\).
| Original arc | Flow before | Update | Flow after |
|---|---|---|---|
| \(s\to a\) | 1 | unchanged | 1 |
| \(s\to b\) | 0 | \(+1\) | 1 |
| \(a\to b\) | 1 | \(-1\) | 0 |
| \(a\to t\) | 0 | \(+1\) | 1 |
| \(b\to t\) | 1 | unchanged | 1 |
The new flow value is \(1+1=2\). At \(a\), inflow is \(1\) and outflow is \(0+1=1\); at \(b\), inflow is \(1+0=1\) and outflow is \(1\). All arc flows are still integers within their capacities. Both arcs leaving \(s\) now carry flow \(1\), so no residual path can leave \(s\). The augmenting path characterization confirms that the value-\(2\) flow is maximum.
Worked Example: No Augmentation Is Available
Let \(V=\{s,a,t,z\}\) and let the only arcs be \(s\to a\) of capacity \(4\), \(a\to s\) of capacity \(2\), and \(z\to t\) of capacity \(3\). Start with zero flow. The original network has no directed path from \(s\) to \(t\): the only arc entering \(t\) comes from \(z\), and there is no arc from the \(s\)-component to \(z\). At zero flow, every reverse residual capacity is \(0\), so the residual network also has no \(s\)-\(t\) path.
| Iteration | Available augmenting path | Update | Flow value |
|---|---|---|---|
| Initial check | None | No augmentation | \(0\) |
The zero flow is feasible and integral. Since no augmenting path exists, the augmenting path characterization says it is maximum. This example includes an isolated source-to-sink route obstruction: the presence of positive capacities elsewhere in a network does not create an augmenting path between the specified terminals.
Common Pitfall: Integer Capacities Are Not Enough
A frequent mistake is to infer that integer capacities force integer bottlenecks regardless of the current flow. Residual capacities depend on both the capacities and the current flow. If the initial flow is fractional, residual capacities can be fractional even when every capacity is an integer.
For a concrete calculation, take \(V=\{s,a,t\}\), with arcs \(s\to a\) of capacity \(2\) and \(a\to t\) of capacity \(3\). Set the initial flow on each arc to \(1/2\). This is feasible: the two arc flows agree at \(a\), and \(1/2\) is between zero and each capacity. The residual capacities on the path \(s\to a\to t\) are \(2-1/2=3/2\) and \(3-1/2=5/2\), so the bottleneck is \(\min(3/2,5/2)=3/2\). The augmentation is not an integer.
The correction is to keep both hypotheses in view. Integer capacities alone do not make residual capacities integral; an integer current flow is needed as well. With integer capacities and an integer feasible initial flow, the Lemma guarantees an integer bottleneck at every step, and the update preserves the integer-flow condition for the next step.
Why the Result Is Useful
The theorem gives more than the existence of an integer maximum flow: it provides an algorithm that finds one, starting even from a nonzero integer feasible flow. In applications with indivisible units, each augmentation moves a whole number of units and the final assignment remains integral. Starting from the zero flow is always allowed when capacities are nonnegative integers, so the theorem in particular guarantees an integral maximum flow in every such network.
Keep the logical roles of the hypotheses separate:
- Integer capacities and an integer current flow make residual capacities and bottlenecks integral.
- Feasibility ensures that augmentation is a valid flow update.
- A finite network and bounded flow value give the finite-augmentation bound.
- No augmenting path at termination gives maximality by the augmenting path characterization.
Check Your Understanding
Answer each question using the definitions and arguments in this tutorial.
- Why does the bottleneck of an augmenting path have to be positive, and what additional hypothesis makes it an integer?
- In the termination proof, why is every feasible flow value at most the sum of capacities on arcs leaving \(s\), even if some arcs enter \(s\)?
- For the network in the reverse-arc example, verify the conservation equation at each internal vertex after the augmentation.
- Can the initial flow value be negative while the termination bound still applies? Explain using the inequality \(|f|\le C\), where \(C\) is the total capacity of arcs leaving \(s\).
- Give a reason the augmenting path characterization is needed in addition to the integrality and termination arguments.