Matching in bipartite graph $|M|\geq \frac {n}{\Delta (G)}$.

Question

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.

Answer 1

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.

Answer 2

According to Kőnig's theorem, proving $\tau_{0}(G)\Delta(G)\ge n$ is sufficient (where $\tau_{0}(G)$ denotes the number of vertex covers). This is true because all edges of a graph are incident on the vertices of a cover, allowing us to establish an upper bound on the size of the graph by counting the edges incident on each vertex of the cover.