Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted


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!

share|cite|improve this answer
Exactly the nudge I needed. Thank you! – wemblem Mar 14 '13 at 0:17

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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