# Thread: Graph theory matching size

1. ## 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.

2. ## Re: Graph theory matching size

If there are no isolated vertices, then all vertices have degree at least 1. Hence, $e(G) \ge \dfrac{n(G)}{2}$. Now, $\Delta(G)$ is the maximum degree of any vertex. If $G$ has $k$ edges and $\Delta(G) = k$, then there exists a vertex incident to every edge in $G$. This would imply that $G$ 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 $k$ edges. Let $G$ be a graph with $k$ edges, and let $H = G-e$ for some $e \in E(G)$. Now, by the IH, $H$ satisfies the hypothesis. Add back $e$. If the smallest integer greater than or equal to $\dfrac{n(G)}{1+\Delta(G)}$ equals the smallest integer greater than or equal to $\dfrac{n(H)}{1+\Delta(H)}$, then a matching in $H$ that satisfies the hypothesis is a matching in $G$ that satisfies the hypothesis. So, figure out when adding $e$ to $H$ will make that number increase. That will help you figure out what you need to prove. (Hint: $\Delta(G) \ge \Delta(H)$)

3. ## 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?

4. ## Re: Graph theory matching size

If $\Delta(G) \ge \Delta(H)$ and $n(G) = n(H)$ then $\dfrac{n(H)}{1+\Delta(H)} \ge \dfrac{n(H)}{1+\Delta(G)} = \dfrac{n(G)}{1+\Delta(G)}$. So, any matching of $H$ that satisfies the hypothesis will still be a matching in $G$ that will satisfy the hypothesis.

5. ## Re: Graph theory matching size

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