Matching!
Augmenting Paths
…
Note that since an augmenting path start from a free vertex and end in another free vertex, the first and last edge in are not in the matching.
The smallest augmenting path is when the first edge = last edge.
We can use induction to show augmenting paths must be of odd length.