Let be a finite simple graph. A matching in is any set of independent edges, we say that is optimal iff there is no other matching in with more edges than . Fix , a simple path in is called alternating w.r.t. iff for every adjacent edges it holds or . An alternating path is called augmenting w.r.t. iff and are not adjacent to edges in .
Ex. from Diestel. Let be a finite simple graph and let be a matching in . Then is optimal if and only if does not admit any augmenting path w.r.t. .
Proof. () If is an augmenting path w.r.t. , then we can improve by taking the symmetric difference .
() Let be a sub-optimal matching and let be a matching greater than , i.e. let , such that is minimum possible.
Then, (*) there is no path such that , , , and for every ; since otherwise we can argue against minimality by considering the matching .
Still imply that there exists . We observe that:
1. There exists s.t. and w.l.o.g. (otherwise we found an augmenting path) .
2. There exists s.t. and w.l.o.g. (by (*)) .
3. There exists s.t. .
Now, if , then we found an augmenting path, otherwise it must be , but then we are in a configuration similar to 1. and we can iterate 2. and 3. Since is finite there must be an augmenting path such that and . Q.E.D.