- #1

tarheelborn

- 123

- 0

## Homework Statement

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)).

## Homework Equations

n(G) = size of the vertex set of G and ∆(G)= maximum degree of v in G

## The Attempt at a Solution

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?