I am reading a book about Graph Algorithms written by Takao Asano.
In the book, the author says the following proposition is true, without a proof.
Is the follwing proposition true or false?
If true, please tell me the proof.
Let $G$ be a graph.
Let $M^{*}$ be a maximum matching in $G$.
Let $M$ be a matching in $G$.Then, there exist $|M^{*}| - |M|$ augmenting paths with respect to $M$ in $G$ which are vertex disjoint.
As always, to compare two matchings, just take the symmetric difference $M \mathbin{\Delta} M^*$. (That is, take all edges in $M$ or $M^*$, but not both.)
The components of the subgraph spanned by $M \mathbin{\Delta} M^*$ are all paths or cycles, because all vertices have degree at most $2$. (At most, they are incident to one edge of $M$ and one edge of $M^*$.) The edges along such a path or cycle must alternate between edges of $M$ and edges of $M^*$. So we have the following types of components:
Even cycles, and paths with an even number of edges. We ignore these, because they have the same number of edges from both matchings.
Paths with one more edge from $M$ than from $M^*$. These would be augmenting paths for $M^*$, and so they can't actually exist, because $M^*$ is a maximum matching.
Paths with one more edge from $M^*$ than from $M$. These are augmenting paths for $M$, so they are what we want.
We know that there must be $k := |M^*| - |M|$ components of the third type, giving us $k$ vertex-disjoint $M$-augmenting paths. We know this because $M \mathbin{\Delta} M^*$ has $k$ more edges from $M^*$ than from $M$, and only components of the third type can give us more edges from $M^*$ than from $M$ (one extra edge per component).