Max-flow min-cut theorem

The greatest value of a feasible source-to-sink flow equals the least capacity of a source-to-sink cut. For a maximum flow, the vertices reachable from the source in the residual graph define a cut whose forward edges are saturated and whose backward edges carry zero flow.

If every directed edge capacity increases by $\epsilon$, a cut of a flow network with $m(S)$ outgoing edges gains $\epsilon m(S)$. By the max-flow min-cut theorem, the new maximum flow value isFor a finite flow network, this is a nondecreasing concave piecewise-linear function, and its active cut can change as $\epsilon$ varies. Two unit-capacity edge-disjoint two-edge source-to-sink paths gain $2\epsilon$, refuting an invariably exact $\epsilon$ increase. If there is a directed source-to-sink path, every cut has at least one outgoing edge and the increase is at least $\epsilon$; without a path it can be zero.

A flow network with integer capacities has a maximum flow whose value on every edge is an integer. The augmenting-path algorithm proves this because every augmentation preserves integrality.

In a finite bipartite graph, the maximum size of a matching equals the minimum size of a vertex cover. It follows by representing matching as an integral flow and vertex covers as finite-capacity cuts.

For a feasible flow $f$, the residual network has forward residual capacity $c(u,v)-f(u,v)$ and reverse residual capacity $f(u,v)$. It records every local increase or cancellation that preserves the capacity constraints.

An augmenting path is a source-to-sink path of positive capacities in the residual network. Increasing the flow by the smallest residual capacity on the path gives another feasible flow of strictly greater value.

The Ford-Fulkerson algorithm repeatedly augments a feasible flow along an augmenting path. When no such path remains, the source-reachable vertices in the residual network define a cut of capacity equal to the flow value, proving optimality by the max-flow min-cut theorem.

Starting from the zero flow with integer capacities, every residual capacity and every augmenting bottleneck is an integer. Each augmentation therefore preserves integer edge flows and raises the flow value by at least one. Since the value is bounded by the total capacity leaving the source, the algorithm terminates after finitely many augmentations with an integral maximum flow.

If one edge leaving the source has capacity $x$, every cut capacity is affine in $x$ with coefficient zero or one. In the 2024 Cambridge Part IB example, cuts of capacities $x+5$ and $14$ are both sharp, giving