# Unions of matchings in a bipartite graph

Question: Let $G$ be a bipartite graph with colour classes $X$ and $Y$. Assume there are two matchings in $G$: $M_1$ which covers $X' \subset X$, and $M_2$ which covers $Y' \subset Y$. Prove that there is a matching that covers $X' \cup Y'$.

What I have so far: If there are no edges between $X'$ and $Y'$ in both $M_1$ and $M_2$, then the two matchings are vertex disjoint and $M_1 \cup M_2$ constitutes a matching which will cover $X' \cup Y'$. But I'm struggling to generalize how one can pick a matching covering $X' \cup Y'$ when $M_1$ and $M_2$ are not vertex disjoint...

-
Ok, so your color class is the division of vertices into two parts that makes the graph bipartite? – dtldarek Mar 13 '13 at 23:03
Yes, that's right. – wemblem Mar 13 '13 at 23:04

Draw a picture, color edges of $M_1$ red and edges of $M_2$ blue. Try starting with subset of $M_1$ that covers $X'$ and adding edges of $M_2$ that cover $Y'$. Any augmenting path will start with blue edge, and then follow (it might just end with the first blue if you are lucky) with red, blue, red, blue, etc. There are two options: you will stay inside $X'$ and $Y'$, but then you will get a cycle (because both $X'$ and $Y'$ are covered by blue or red edges), or you will get outside, but then it is fine, because it is safe to add that edge.