Show that for two maximal matchings $M_1,M_2$ holds $\lvert M_1 \rvert \le 2\lvert M_2 \rvert$

Question

I am working on the following exercise:

Let $G(V,E)$ be an undirected graph and let $M_1$ and $M_2$ be two maximal matchings in $G$. Prove that $\lvert M_1 \rvert \le 2\lvert M_2 \rvert$.

I do not see how I could prove that. Could you help me?

Answer 1

This can be proved by contradiction.

Suppose that, on the contrary, $\lvert M_1 \rvert > 2\lvert M_2 \rvert.$

At most $2\lvert M_2 \rvert$ edges of $ M_1$ can have a vertex in common with an edge of $ M_2$ and so there is at least one edge which doesn't. This edge can be added to $M_2$ which therefore cannot have been a maximal matching.