• Support PF! Buy your school textbooks, materials and every day products Here!

Graph Theory - Matching Size

  • #1
123
0

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?
 

Answers and Replies

  • #2
Zondrina
Homework Helper
2,065
136

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?
 
  • #3
123
0
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.
 
  • #4
Zondrina
Homework Helper
2,065
136
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.
 
  • #5
123
0
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...
 
  • #6
Zondrina
Homework Helper
2,065
136
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:

Related Threads on Graph Theory - Matching Size

  • Last Post
Replies
1
Views
1K
Replies
0
Views
4K
  • Last Post
Replies
3
Views
800
Replies
2
Views
1K
  • Last Post
Replies
1
Views
557
  • Last Post
Replies
6
Views
686
  • Last Post
Replies
2
Views
2K
Replies
5
Views
2K
  • Last Post
Replies
1
Views
2K
Replies
17
Views
2K
Top