1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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

union of matchings

I hope this helps $\ddot\smile$

$\endgroup$

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.