the max-flow min-cut theorem
Two questions about a pipe network look unrelated: how much can you push from pump to drain, and how cheaply can you cut pipes to disconnect them? The max-flow min-cut theorem says they have the same answer, exactly. The most you can ship equals the least it costs to sever the route. This surprising equality is the centerpiece of flow theory and your first taste of linear-programming duality.
The theorem states: the maximum value of any s-t flow equals the minimum capacity of any s-t cut. The 'at most' half is easy — every unit of flow must cross any cut from the s-side to the t-side, so value <= cut capacity for every cut, hence max-flow <= min-cut. The 'at least' (equality) half is the heart, and the proof is constructive: run an augmenting-path method until no augmenting path exists in the residual graph. At that point, let S be all vertices still reachable from s in the residual graph and T the rest. Then s is in S, t is in T, every edge from S to T must be saturated (else it would leave residual capacity and t would be reachable), and every edge from T to S carries zero flow. So the value of this flow equals the capacity of this cut — a flow and a cut with the same number, which by the 'at most' half must both be optimal.
Three things equal each other at the optimum: a max flow exists, a min cut exists, and they have the same value, which is also why an augmenting-path algorithm is correct (it stops exactly when flow meets a cut). The min cut also names the true bottleneck and gives a certificate: you can prove a flow is maximum by exhibiting a cut of equal capacity, with no need to trust the algorithm. This is LP duality in miniature — max flow is a primal LP, min cut its dual — and the same pattern reappears throughout optimization. Honest caveat: the equality is exact for real-valued capacities, but the constructive proof's termination needs care (integer or rational capacities, or Edmonds-Karp's shortest-path rule).
Take s -> a (3), s -> b (2), a -> t (2), b -> t (3), a -> b (1). The max flow has value 5 (s->a=3, s->b=2, a->t=2, a->b=1, b->t=3). To certify it, search cuts until one equals 5; e.g. S = {s}, T = {a,b,t} has capacity 3 + 2 = 5, matching the flow and proving it maximum.
Find a cut whose capacity equals your flow's value and you have proved the flow optimal — no faith in the algorithm required.
The theorem is an existence-and-equality statement, not an algorithm. It guarantees max-flow = min-cut but says nothing about how fast you find them; and naive Ford-Fulkerson can fail to terminate on irrational capacities even though the equality still holds.