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.**