Graph theory matching size

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)

vertices.

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.

Re: Graph theory matching size

If there are no isolated vertices, then all vertices have degree at least 1. Hence, . Now, is the maximum degree of any vertex. If has edges and , then there exists a vertex incident to every edge in . This would imply that has only one component. Why are you limiting to only connected graphs that also happen to be stars?

Instead, assume the hypothesis holds for any graph with fewer than edges. Let be a graph with edges, and let for some . Now, by the IH, satisfies the hypothesis. Add back . If the smallest integer greater than or equal to equals the smallest integer greater than or equal to , then a matching in that satisfies the hypothesis is a matching in that satisfies the hypothesis. So, figure out when adding to will make that number increase. That will help you figure out what you need to prove. (Hint: )

Re: Graph theory matching size

The number will increase when you add e back to a vertex in H with the maximum degree. Is that what you're thinking?

Re: Graph theory matching size

If and then . So, any matching of that satisfies the hypothesis will still be a matching in that will satisfy the hypothesis.

Re: Graph theory matching size

(Oh, unless deleting from leaves an isolated vertex)... so, you need to be careful when picking . If removing any will leave an isolated vertex, then you know something else about , and you can still show that the graph satisfies the hypothesis.