Certify a maximum flow by a cut

Try

A flow network sends material from source s to sink t through directed edges with nonnegative capacities. At every other vertex, incoming and outgoing flow must balance. A path with available capacity seems an obvious improvement, but earlier choices may need to be undone. Residual reverse edges encode exactly that permission and are essential to the max-flow theorem.

Predict

Predict the meaning of a cut. Divide vertices into a source side S containing s and a sink side containing t. Every unit of net flow must cross from S outward, though some flow may cross back. The net value is forward flow minus backward flow. Ignoring the backward term gives an incorrect equality; replacing forward flows by capacities gives the correct universal upper bound.

Experiment

Consider edges s→a of capacity three, s→b of capacity two, a→t of capacity two, b→t of capacity three, and a→b of capacity one.

Route	Flow assigned
s→a→t	2
s→b→t	2
s→a→b→t	1

The total is five. Check conservation at a and b and every edge capacity. The cut containing only s has capacity five, so this feasible flow and cut together certify optimality.

Understand

For each original edge u→v with flow f and capacity c, residual capacity c−f permits increasing its flow, while a reverse residual edge v→u with capacity f permits decreasing it. If the original network has edges in both directions, track their residual contributions separately or with an equivalent combined convention. An s-t residual path can be augmented by its smallest residual capacity; conservation persists and the total value increases by that amount. Starting from zero and repeating gives Ford–Fulkerson’s method.

Apply

If no augmenting path exists, let S be all residual-reachable vertices from s. The sink lies outside S. Every original edge from S outward is saturated, because otherwise its residual edge would reach farther. Every original edge from outside into S has zero flow, because positive flow would create a reverse residual edge leaving S. Summing conservation over S therefore shows the flow value equals the cut capacity. Since every feasible flow is bounded by every cut, both are optimal. This proves max-flow/min-cut and gives a verifiable certificate, not merely a stopping heuristic.

Continue

With integer capacities, zero initialization and integral augmentations preserve integrality, and each augmentation increases value by at least one. A finite cut bounds the value, proving termination; the resulting iteration bound depends on capacity magnitude and is not polynomial in its bit length. Choosing shortest residual paths gives stronger algorithmic guarantees, requiring an additional distance-monotonicity analysis. Arbitrary irrational capacities can defeat the simple termination proof. In an implementation task, test conservation, capacities and the final cut independently, and distinguish a maximum flow from a maximum number of edge-disjoint paths unless unit-capacity assumptions justify that interpretation.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with turn disjoint paths into a cut problem.