Graph Theory - Matching Size

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?

Related Calculus and Beyond Homework Help News on Phys.org
Zondrina
Homework Helper

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?
I'm assuming by $e(G)$ you mean the number of edges in $G$.

Also, you stated this :

$∆G$= maximum degree of $v$ in $G$
I'm pretty sure you mean the maximum degree of the graph.

For the base case, assume $e(G) = 1$. You have 2 nodes, so the maximum degree of either node is 1. What else can you conclude?

Yes, you are absolutely right. It has been a VERY long day.

Following what you said re the base case, we can say that G has a match of size at least 2/(1+1) = 1, which is clear. Now we could suppose that the theorem holds for all graphs with k or fewer edges and consider a graph with k+1 edges. If we have this k+1-edge graph and delete one of the edges, then we could apply the IH. I am just not sure how to get there from here.

Zondrina
Homework Helper
Yes, you are absolutely right. It has been a VERY long day.

Following what you said re the base case, we can say that G has a match of size at least 2/(1+1) = 1, which is clear. Now we could suppose that the theorem holds for all graphs with k or fewer edges and consider a graph with k+1 edges. If we have this k+1-edge graph and delete one of the edges, then we could apply the IH. I am just not sure how to get there from here.
You're assuming none of the nodes on the graph are isolated. So when you say $k+1$ edges, it's not as if that condition is changing.

But no node is isolated by the hypothesis. I'm not sure what you mean about k+1 edges not changing since k is variable. I am simply not seeing this at all...

Zondrina
Homework Helper
But no node is isolated by the hypothesis. I'm not sure what you mean about k+1 edges not changing since k is variable. I am simply not seeing this at all...
Your induction assumption would be to assume the hypothesis holds for $e(G) = k$. Stop for a moment and visualize how many nodes there would be on this graph because it will be helpful in the next step.

Now show it holds for $e(G) = k+1$.

Hint: An edge can have how many nodes attached?

Last edited: