# Max-flow min-cut

From Algowiki

## Max-flow min-cut theorem

Let , , and for let and be real values such that and is a feasible -flow. Then the following three statements are equivalent:

- The flow value of is maximum among all feasible -flows.
- There is a saturated cut.
- There is no flow-augmenting path from to .

## Proof

First suppose there is no flow-augmenting path from to . Let denote the set of all nodes reachable from via flow-augmenting paths, and let . Then we have and . Obviously, is saturated.

Next suppose there is a saturated cut. No flow can carry more units of flow value from to than the capacity of any -cut allows. Consequently, is maximum.

Finally suppose is maximum. Clearly, then a flow-augmenting path from to cannot exist.