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 .
Finally suppose is maximum. Clearly, then a flow-augmenting path from to cannot exist.