Max-Flow Min-Cut

Max-Flow Min-Cut applies Edmonds–Karp to the displayed directed network. Each edge is labelled flow/capacity, followed by its forward and backward residual capacities. Orange edges are the current augmenting path; red edges form the final minimum cut. Blue nodes remain reachable from S in the final residual graph.

Each augmentation sends the bottleneck amount through an S→T residual path. A positive backward residual capacity can cancel flow on an earlier edge, which is why the residual graph is essential. At termination no residual path reaches T. The total flow then equals the capacity of the displayed cut.