How much water can flow from source to sink through a network of capacity-limited pipes? Keep finding a path with spare capacity and push flow along it, until none remains. The beautiful theorem: the maximum flow you can push EXACTLY equals the capacity of the cheapest ‘cut’ that separates source from sink. The bottleneck is the limit, provably. Slide to push flow.
The max-flow problem sends as much flow as possible from a source s to a sink t, each edge bounded by its capacity, with flow conserved at every other node. Ford–Fulkerson repeatedly finds an AUGMENTING PATH with residual capacity and pushes flow until none exists. The max-flow min-cut theorem proves the maximum flow equals the minimum CUT — the smallest total capacity of edges whose removal disconnects s from t. Here the max flow is 5, matching the cut {s,a}. It models logistics, matching, and image segmentation. A fail-loud self-check throws unless the computed max flow equals 5 (= the min cut). ◆ real combinatorial optimization, node-verified.
Shown on a small fixed network; the max-flow = min-cut equality is an exact theorem. Ford–Fulkerson’s running time depends on the path-choice rule (Edmonds–Karp uses BFS for a polynomial bound).