Given a bipartite graph, with n edges. Prove that there exist matching M such that $|M|\geq \frac {n}{\Delta (G)}$.

Can someone check my solution.

Can this be proved by induction, over $\Delta$.

For, $\Delta=1$ it is easy, M=E. Now for $\Delta \geq 2$.

For every node with $d(v)=\Delta$, we can remove one edge. In that graph there exist M-matching such that $|M|(\Delta-1)\geq n-s$, where s is number of removed edges. Now, if every removed edge, has one end in M, $|M| \geq s$ so $|M| \geq \Delta n$. If it is not true, there is removed edge with no nodes in M. First, if there is another edge from v, with node in M, we can replace this edges. Else, there is bigger maching M', and we look that one.

Sorry for my bad English.


It's not true that if every removed edge has one end in $M$, then $|M|\ge s$. Even if the removed edges are a matching (which you haven't specified) you could have two of the removed edges going to one edge in $M$.

What you need for this proof to work is a more powerful lemma: that you can find a matching in the original graph that covers all vertices of degree $\Delta$. Then you can proceed as in the proof:

  • The lemma finds you a matching $M_1$ of size $s$.
  • The inductive step finds you a matching $M_2$ such that $|M_2|(\Delta-1) \ge n-s$.

Now let $M$ be the larger of the two matchings $M_1$ and $M_2$ (picking arbitrarily if there's a tie). We know both that $|M| \ge s$ and that $|M|(\Delta-1) \ge n-s$, and so (just as in your proof) we get $|M| \Delta \ge n$ by adding these together.


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.