Augmenting paths of two matchings

Question

Given a graph $G(V, E)$ and two matchings $M \subset E$ and $M' \subseteq E$ with $|M'| > |M|$, how can one prove that $M\oplus M'$ ($\oplus$ denotes the symmetric difference) must contain at least $|M'|-|M|$ augmenting paths of $M$? I know that there have to exist some $M$-augmenting paths since $M$ is not a maximum matching, but I don't really know how to prove the above.

Answer 1

If $M$ and $M'$ have $k$ edges in common, then $M \oplus M'$ has $|M|-k$ edges from $M$, and $|M'|-k$ edges from $M'$.

In particular, there are still $|M'|-|M|$ more edges from $M'$ than from $M$ in the symmetric difference.

This excess of $|M'| - |M|$ simply cannot be accomplished by fewer than $|M'|-|M|$ augmenting paths. To see this, you should convince yourself that:

1. Any component of $M \oplus M'$ that's not an augmenting path, there are equally many edges from $M$ and from $M'$, so it doesn't help at all.
2. Any component of $M \oplus M'$ that is an $M$-augmenting path has only one more edge from $M'$ than from $M$.
3. We could also have components that are $M'$-augmenting paths, which are even less useful: they have more edges from $M$ than from $M'$.

Therefore, to get to a difference of $|M'|-|M|$ in the number of edges, we need at least $|M'|-|M|$ or more $M$-augmenting paths.