Matchings in a graph

Question

Let $M$ and $N$ be matchings in a graph $G$ with $|M| > |N|$. Prove their exist matchings $M'$ and $N'$ in $G$ such that $|M'| = |M| - 1$ and $|N'| = |N| + 1$, and $M'∪ N' = M ∪ N$ and $M'∩ N' = M∩ N$.

Let $M$ and $N$ be nonempty matchings with $|M| > |N|$. It's extremely trivial that choosing $M'=N$ and $N'=M$, so obviously we are looking for two different matchings completely. Consider two cases: $M$ is not maximal, and $M$ is maximal. Notice $N$ is not maximal in either case.

1. $M$ is not maximal. Then there exists a (shortest?) $M$-augmented path in $G$, call it $P$. Choose $N'=E(P)-M$, the edges in the augmented path, but not in the matching. Since this $M$-augmented path is the shortest such one, $|N'| = |M|$ There also exists an $N$-augmented path, say $Q$, and we can choose $M' = E(Q) - N$...I'm not sure if this is going to work out..

2. $M$ is maximal, I'm not sure how to find the $M'$, but I can intuitively understand that it exists. It's like you choose the "opposite" of it.

Am I way off base here?

Answer 1

You are not off base by much, but you are going in a wrong direction.

Hint:

• How many (at most) vertices in $M$ can be covered by $N$?
• Take any uncovered vertex, how can you modify $N$ so that it covers that vertex in addition to all it covers now?

I hope it helps $\ddot\smile$