bipartite graph matching

Question

can anybody please give me a hand on this lemma on bipartite graph matching please?

Let $M_1$ and $M_2$ be two arbitrary matchings in a bipartite graph G with bipartition $\{P,Q\}$ (of its vertex set). Prove that there exist some matching M such that matches all vertices in P that are matched by $M_1$ and all vertices in Q that are matched by $M_2$.

I really don't know how to prove this lemma. I can draw some examples, and it is clearly true. But I can't think of how to prove it. I thought about taking union of two matchings, and then somehow take off some parts overlapping? Or should I think about augmenting path which has edges alternating between two matchings? Can anybody please give me a hand. Thank you so much.

Answer 1

Hint:

• Color the edges of $M_1$ red and direct them from $P$ to $Q$.
• Color the edges of $M_2$ blue and orient them from $Q$ to $P$.
• Union $M_1 \cup M_2$ is a (possibly non-simple) graph that has vertices of a degree at most $2$, so it is a collection of directed paths and cycles.
• For each connected component pick the color with which the path starts (for cycles it doesn't matter which you choose).

I hope this helps $\ddot\smile$