the residual graph

Suppose you have already routed some water and want to know what moves remain. Two kinds of move are available: push more along a pipe that still has spare room, or undo some water you already sent by pushing it back the other way. The residual graph is the bookkeeping that captures exactly these remaining options after a partial flow — and the second, the ability to cancel, is the subtle ingredient that makes flow algorithms correct.

Given a flow f on network G, the residual graph Gf has the same vertices and, for each original edge (u, v) with capacity c and flow f(u, v), up to two residual edges. A forward residual edge u -> v with residual capacity c(u, v) - f(u, v), representing spare room you can still fill. And a backward residual edge v -> u with residual capacity f(u, v), representing flow you could cancel by rerouting. For instance, if c(u, v) = 5 and f(u, v) = 3, then Gf has u -> v of residual capacity 2 and v -> u of residual capacity 3. Edges with zero residual capacity are simply omitted. To improve a flow you find any path of positive residual capacity from s to t in Gf and push along it; pushing on a backward edge means reducing the original flow there.

The residual graph is the engine of every augmenting-path algorithm. Augmenting paths, Ford-Fulkerson, Edmonds-Karp, and Dinic all operate on Gf, not G. The backward edges are the crucial twist: without them, a greedy push could paint itself into a corner with no way to reroute, and you might stop short of the true maximum. With them, you can always undo a bad commitment, which is exactly what lets the method reach optimality. The residual graph also delivers the min cut for free: when no s-t path remains in Gf, the vertices still reachable from s form the s-side of a minimum cut.