Graph Theory37 sections · 1633 units
Open in Course

Why Residual Graph Works

(No augmenting paths left)

At max flow, there is no augmenting path from ss to tt in the residual graph.

This means tt is unreachable from ss using edges with remaining capacity. The vertices reachable from ss form set SS. Since totinSt otin S, you have tTt \in T. Edges crossing from SS to TT are saturated because they have no remaining capacity. These saturated edges are the bottleneck. Their total capacity equals the max flow. The max-flow min-cut theorem guarantees this.