# Maximum number of augmenting paths in symmetric difference of maximum and another matching

This tutorial (page 22) on Hopcroft-Karp algorithm for maximum bipartite matching states the following:

Let $M^*$ be a maximum matching, and let $M$ be any matching in $G = (V, E)$. ...

Let us consider the graph $G'=(V, M \oplus M^*)$. It contains at most $|M^*|-|M|$ augmenting paths with respect to $M$.

Here $M\oplus M^*$ is the symmetric difference between $M$ and $M^*$. But how does the last line (It contains at most $|M^*|-|M|$ augmenting paths with respect to $M$) follow?

-
Each augmenting path increases the size of the matching by $1$. – Andrew Salmon May 26 '13 at 7:15
@AndrewSalmon But how does it prove the statement? Can you explain a bit more? – f.nasim May 26 '13 at 10:32
The size of the matching $M$ is $|M|$. So you're starting with size $|M|$--then, each augmenting path can increase the size of the matching by $1$, so after $|M^*| - |M|$ augmenting paths there are $|M| + |M^*| - |M| = |M^*|$ augmenting paths. There can't be more, because $M^*$ is a maximum matching. – Andrew Salmon May 26 '13 at 18:41
@AndrewSalmon Got it. – f.nasim May 27 '13 at 4:50

Each augmenting path increases the size of the matching by $1$.
The size of the matching $M$ is $|M|$. So you're starting with size $|M|$: then, each augmenting path can increase the size of the matching by $1$, so after $|M^∗|−|M|$ augmenting paths there are $|M|+|M^∗|−|M|=|M^∗|$ augmenting paths. There can't be more, because $M^∗$ is a maximum matching.