5.3. Existence of Integral Flows*

A question that is important in subsequent chapters is whether we can guarantee that a maximum flow algorithm computes an \(st\)-flow that sends an integral amount of flow across every edge in \(G\). We observe that each of the maximum flow algorithms discussed in this chapter computes an integral maximum flow if all edge capacities are integers.¹

Observation 5.35: If the edge capacities are integers, then the maximum \(st\)-flow computed by any of the algorithms discussed in this chapter sends an integral amount of flow across every edge of \(G\).

Proof: Each maximum flow algorithm starts by setting \(f_{x,y} = 0\) or possibly \(f_{x,y} = u_{x,y}\) if \(x = s\) and the algorithm is a preflow-push algorithm. Thus, initially, the flow across every edge is integral. For a preflow-push algorithm, this in turn implies that the excess of every node is integral.

Every time an augmenting path algorithm changes the current flow \(f\), it sends an amount of flow along the path that matches the minimum residual capacity of the edges on the path. Since the current edge flows and edge capacities are integral, the residual capacities are also integral, so the flow along every edge changes by an integral amount and thus remains integral.

When a preflow-push algorithm changes the flow along an out-edge \((x, y)\) of some overflowing vertex \(x\), the flow it sends along the edge \((x, y)\) is the minimum of \(x\)'s excess and the residual capacity of the edge \((x, y)\). Since both are integral, the flow along the edge \((x, y)\) and the excesses of \(x\) and \(y\) remain integral. ▨

Corollary 5.36: If the edge capacities are integers, then there always exists a maximum flow that sends an integral amount of flow across every edge of \(G\).