Prove that every graph G without isolated vertices has a matching of size at least n(G)/(1+∆(G)). (Hint: Apply induction on e(G)).
I have started this problem several times, but this is my latest attempt:
For the base case, let every edge of G be incident to a vertex with degree = 1. Then each component of G has, at most, one vertex with degree > 1 which implies that each component is a star. A matching can be formed by using one edge from each component. The number of components is n(G)/∆(G)+1 since each component has 1 + dG(v)
Now suppose the hypothesis is true for G with k edges and consider a graph H with k+1 edges. Then ∆(G) would have to be k, right? And then apply the IH?
Thanks for any help.