Max-Flow Min-Cut Theorem

The duality result stating that the maximum s-t flow equals the minimum-capacity s-t cut in any network.

Statement

In a flow network, an s-t cut partitions the vertices into a set S containing the source and a set T containing the sink; its capacity is the total capacity of edges from S to T. The max-flow min-cut theorem states that the maximum value of any s-t flow equals the minimum capacity over all s-t cuts.

Why it holds

Kronos motion — burner power flow

Any flow is bounded above by any cut's capacity, since all flow must cross the cut. When an augmenting-path algorithm terminates, the set of nodes reachable from the source in the residual graph defines a cut whose forward edges are all saturated and whose backward edges carry no flow. The flow across that cut equals its capacity, so flow meets the upper bound and both are optimal.

Recovering the cut

python

def min_cut(residual, s):
    seen, stack = {s}, [s]
    while stack:
        u = stack.pop()
        for v in residual[u]:
            if residual[u][v] > 0 and v not in seen:
                seen.add(v); stack.append(v)
    # cut edges: original u->v with u in seen, v not in seen
    return seen

Consequences

Menger's theorem: max edge-disjoint paths equals min edge cut, a unit-capacity special case.
Koenig's theorem on bipartite graphs: max matching equals min vertex cover.
Project-selection and image-segmentation problems reduce to min cut.
Reliability and network-vulnerability analysis identify the bottleneck via the min cut.

Practical use

Compute a max flow with Dinic or Edmonds-Karp, then read off the min cut from residual reachability. The theorem is the correctness proof for every augmenting-path method and a modelling tool that turns partition problems into flow problems.