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...

  • $\begingroup$ Ok, so your color class is the division of vertices into two parts that makes the graph bipartite? $\endgroup$
    – dtldarek
    Mar 13 '13 at 23:03
  • $\begingroup$ Yes, that's right. $\endgroup$
    – 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.

Good luck!

  • $\begingroup$ Exactly the nudge I needed. Thank you! $\endgroup$
    – wemblem
    Mar 14 '13 at 0:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.