Augmenting paths are neat:
- An augmenting path has one more white edge than blue. Why?
- Flipping the color of edges on the augmenting path results in a
valid matching. Why?
- Therefore, after flipping the colors, our matching is bigger by
one edge.
Next: Algorithm
Up: MIN-CUT MAX-FLOW
Previous: Augmenting Path