# Graph theory matching size

• Sep 30th 2013, 12:26 PM
tarheelborn
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.
• Sep 30th 2013, 03:09 PM
SlipEternal
Re: Graph theory matching size
If there are no isolated vertices, then all vertices have degree at least 1. Hence, $\displaystyle e(G) \ge \dfrac{n(G)}{2}$. Now, $\displaystyle \Delta(G)$ is the maximum degree of any vertex. If $\displaystyle G$ has $\displaystyle k$ edges and $\displaystyle \Delta(G) = k$, then there exists a vertex incident to every edge in $\displaystyle G$. This would imply that $\displaystyle 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 $\displaystyle k$ edges. Let $\displaystyle G$ be a graph with $\displaystyle k$ edges, and let $\displaystyle H = G-e$ for some $\displaystyle e \in E(G)$. Now, by the IH, $\displaystyle H$ satisfies the hypothesis. Add back $\displaystyle e$. If the smallest integer greater than or equal to $\displaystyle \dfrac{n(G)}{1+\Delta(G)}$ equals the smallest integer greater than or equal to $\displaystyle \dfrac{n(H)}{1+\Delta(H)}$, then a matching in $\displaystyle H$ that satisfies the hypothesis is a matching in $\displaystyle G$ that satisfies the hypothesis. So, figure out when adding $\displaystyle e$ to $\displaystyle H$ will make that number increase. That will help you figure out what you need to prove. (Hint: $\displaystyle \Delta(G) \ge \Delta(H)$)
• Sep 30th 2013, 03:34 PM
tarheelborn
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?
• Sep 30th 2013, 03:43 PM
SlipEternal
Re: Graph theory matching size
If $\displaystyle \Delta(G) \ge \Delta(H)$ and $\displaystyle n(G) = n(H)$ then $\displaystyle \dfrac{n(H)}{1+\Delta(H)} \ge \dfrac{n(H)}{1+\Delta(G)} = \dfrac{n(G)}{1+\Delta(G)}$. So, any matching of $\displaystyle H$ that satisfies the hypothesis will still be a matching in $\displaystyle G$ that will satisfy the hypothesis.
• Sep 30th 2013, 03:45 PM
SlipEternal
Re: Graph theory matching size
(Oh, unless deleting $\displaystyle e$ from $\displaystyle G$ leaves an isolated vertex)... so, you need to be careful when picking $\displaystyle e$. If removing any $\displaystyle e$ will leave an isolated vertex, then you know something else about $\displaystyle G$, and you can still show that the graph satisfies the hypothesis.