Let’s suppose that
\(M\) is a matching in
\(G\) and that
\(M\) is maximum. We will show that there are no augmenting paths with respect to
\(M\text{.}\) Suppose, for the sake of contradiction, that there is an augmenting path
\(P\) with respect to
\(M\text{.}\) By our lemma, we can create a new matching
\(M'\) by removing the edges of
\(M\) along the path and adding the other edges of the path to the matching. The new matching
\(M'\) has size
\(|M| + 1\text{,}\) which contradicts the assumption that
\(M\) is maximum. Therefore, there are no augmenting paths with respect to
\(M\text{.}\)
Next, we will show that if there are no augmenting paths with respect to a matching
\(M\) in
\(G\text{,}\) then
\(M\) is maximum. We will do this using the technique of proof by
contrapositive: we will show that if
\(M\) is not maximum, then there exists an augmenting path with respect to
\(M\text{.}\) Let
\(M'\) be a maximal matching in
\(G\text{,}\) and note that
\(|M'| > |M|\text{.}\) Consider the symmetric difference
\((M \cup M')\setminus (M\cap M')\text{,}\) and consider the subgraph
\(H\) of
\(G\) containing those edges. In
\(H\text{,}\) each vertex has degree
\(1\) or
\(2\text{,}\) since each vertex is incident to at most one edge from
\(M\) and at most one edge from
\(M'\text{.}\) Thus, the connected components of
\(H\) are paths and cycles, and if they are cycles, the length of the cycle is even, since the edges alternate between those in
\(M\) and those in
\(M'\text{.}\) The graph
\(H\) has more elements of
\(M'\) than of
\(M\text{,}\) so there must be at least one path component in
\(H\) that has more edges from
\(M'\) than from
\(M\text{.}\) Such a path must start and end with edges from
\(M'\text{,}\) and thus starts and ends at vertices not covered by
\(M\text{.}\) Therefore, this path is an augmenting path with respect to
\(M\text{,}\) and we are done.
