Short note: Max-flow min-cut theorem

Flow network: a directed graph with a source s, a sink t, and a capacity c(u,v) ≥ 0 on each edge. A flow f assigns f(u,v) ≤ c(u,v) to each edge so that, at every vertex other than s and t, flow in = flow out (conservation). Its value is the net flow leaving s.

A cut (S, T) splits the vertices into S containing s and T containing t. Its capacity is the sum of capacities of the edges going from S to T.

Max-flow min-cut theorem (Ford–Fulkerson): in any flow network, the maximum value of a flow equals the minimum capacity of a cut.

Why: the flow across any cut is at most its capacity, so max flow ≤ min cut. When no augmenting path exists in the residual graph, the vertices reachable from s form S, every edge S→T is full and every edge T→S is empty, so the flow equals that cut's capacity.

Ford–Fulkerson method: start with zero flow; repeatedly find an augmenting path from s to t in the residual graph, push the bottleneck amount along it, and stop when none exists.

Example: edges s→a 3, s→b 2, a→b 1, a→t 2, b→t 3.

Now no path remains. Max flow = 5. The cut S = {s}, T = {a, b, t} has capacity 3 + 2 = 5, equal to the flow, so it is a minimum cut.

Uses: network routing, bipartite matching, project scheduling.