Graph Theory into

Question

Let $M$ and $N$ be matchings in a graph $G$ with $\lvert M\rvert > \lvert N\rvert$. Prove that there exists matchings $M'$ and $N'$ such that $\lvert M'\rvert = \lvert M\rvert-1$, and $\lvert N'\rvert = \lvert N\rvert+1$, and $M'\cup N'= M \cup N$, and $M'\cap N'= M \cap N$.

Answer 1

The instructions are very instructive I think. Since $M\cap N=M'\cap N'$ for edges occurring in both matchings you need not think at all.

Since $\lvert M\rvert>\lvert N\rvert$ however $M$ and $N$ differ and there is some $m_0\in M$ such that $m_0\not\in N$. Since $N$ is a matching there is $n_0\in N$ with $n_0\not\in M$ and $m_0\cap n_0\neq\emptyset$ and so on. Collect $(m_i)_i$ and $(n_i)_i$ until one of $m_{k+1}\in(m_i)_{i\leq k}$ or $n_k\in (n_i)_{i<k}$ occurs.

You probably already guessed it, you are going to exchange $m_i$ and $n_j$ in the end.

The only thing to observe is that each of this exchanges leaves again matchings with the exactly same edges (hence $M\cup N=M'\cup N'$) but possibly one edge more/less to $M$ and one edge less/more to $N$. You will not touch $M\cap N$ as neither of the initial matchings has an adjacent edge. You will eventually succeed (arrive at $M'$ and $N'$ of desired cardinalities), since $\lvert M\rvert>\lvert N\rvert$.

By construction you can also see that for every $0\leq i \leq \lvert M\rvert-\lvert N\rvert$ you can construct such $M'$, $N'$ with $\lvert M'\rvert=\lvert M\rvert - i$ and $\lvert N'\rvert=\lvert N\rvert +i$ and the union and intersection property as stated above.