Let G=(V,E) be a graph which contains no loops.
Denote the maximum degree of vertices in G by D.
Denote the maximum matching of G by M.
Let |V|=n
Prove that if D is at least 1,
then |M| is at least n/(D+1).
Any insights on this question?
I have been trying to prove it for a few hours, and I don't think I have got any breakthroughs yet =/