Flows, cuts, and integral flow

Use a finite directed network with distinct source $s$ and sink $t$, nonnegative finite edge capacities, and for simplicity no edges entering $s$ or leaving $t$. A flow assigns each directed edge a nonnegative number at most its capacity. At every other vertex, total incoming flow equals total outgoing flow. The flow value is total flow leaving $s$, equivalently total flow entering $t$. Conservation lets traffic split and merge, but does not permit an intermediate vertex to create or absorb it.

For a cut $S$ containing $s$ and excluding $t$, add conservation over all vertices in $S$. Contributions from internal edges cancel, leaving flow value equal to outward flow across the cut minus inward flow. Dropping the nonnegative inward term and bounding each outward edge by its capacity gives an upper bound on every feasible flow. This derivation works regardless of how routes were selected; a narrow boundary limits all possible plans simultaneously.

The residual network records allowed adjustments. An original edge with capacity $c$ and flow $f$ has forward residual capacity $c-f$ and a backward cancellation capacity $f$. If both original directions exist, keep their adjustment records distinct or combine them consistently. An $s$–$t$ path with positive residual capacities allows an augmentation by the smallest residual capacity on that path. A backward step subtracts earlier flow; it does not claim that the physical edge has reversed direction.

If no residual route reaches $t$, let $S$ be the vertices reachable from $s$ in the residual network. Every original edge leaving $S$ is saturated, or its unused capacity would make another vertex reachable. Every original edge entering $S$ carries zero flow, or its cancellation edge would leave $S$. The cut identity then gives $|f|=c(S)$. Since no flow exceeds any cut, equality proves both objects optimal. For arbitrary real capacities, an optimum exists because the feasible flows form a nonempty closed bounded subset of a finite-dimensional box and the value is continuous. Such an optimum cannot have a residual augmenting path, so the same cut argument proves the theorem.

When every capacity is an integer, begin with zero flow and use integral augmentations. Residual capacities remain integers, so each augmentation increases value by at least one. The value is bounded by the finite total capacity out of the source, hence the process terminates at an integral maximum flow. This proves existence of an integer optimum; it does not claim every optimal flow is integral. With arbitrary real capacities, careless augmenting-path choices need not terminate, although the theorem still holds.

This integrality explains why flow can solve discrete selection problems. To model a bipartite matching, orient eligibility edges from left to right, add unit-capacity edges from a new source to each left vertex and from each right vertex to a new sink, and give eligibility edges unit capacity. An integral flow selects whole left-to-right edges, with source and sink capacities preventing endpoint reuse. Unit edge capacities likewise turn disjoint-path questions into flow questions once direction and any internal-vertex restrictions are modeled correctly.