Krdytkyu

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:

1. Even cycles, and paths with an even number of edges. We ignore these, because they have the same number of edges from both matchings.




2. 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.




3. 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).