Can Every Graph Guarantee a Minimum Matching Size?

[tarheelborn]

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?

 

[STEMucator]

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?

 

[tarheelborn]

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.

 

[STEMucator]

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.

 

[tarheelborn]

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

 

[STEMucator]

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?