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

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

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

STEMucator
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: