Graph Theory - Matching Size

In summary, to prove that every graph G without isolated vertices has a matching of size at least n(G)/(1+∆(G)), we can use induction on the number of edges in G. For the base case, we assume that G has only one edge and show that there is a matching of size at least 1. Then, we assume that the hypothesis holds for all graphs with k or fewer edges and consider a graph with k+1 edges. By deleting one of the edges, we can apply the induction hypothesis and show that there is still a matching of size at least n(G)/(1+∆(G)). This is because each edge can have at most two nodes attached to it, and the maximum degree of
  • #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?
 
Physics news on Phys.org
  • #2
tarheelborn said:

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
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
tarheelborn said:
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
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
tarheelborn said:
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:

1. What is "matching size" in graph theory?

In graph theory, matching size refers to the number of edges in a matching, which is a subset of edges in a graph that do not share any common vertices.

2. How is matching size calculated in a graph?

Matching size can be calculated by counting the number of edges in a matching. Alternatively, it can also be calculated by finding the maximum number of edges that can be included in a matching in a given graph.

3. What is the significance of matching size in graph theory?

Matching size is an important concept in graph theory as it provides information about the maximum number of independent pairs in a graph. It also has practical applications in areas such as network flow, scheduling, and resource allocation problems.

4. Can the matching size of a graph be greater than the number of vertices?

No, the matching size of a graph cannot be greater than the number of vertices. This is because each vertex can only be included in one edge of a matching, and thus the maximum number of edges in a matching is equal to the number of vertices in the graph.

5. How does matching size relate to other concepts in graph theory?

Matching size is closely related to other concepts in graph theory such as vertex cover, independent set, and maximum flow. It also has connections to other mathematical fields such as combinatorics and linear algebra.

Suggested for: Graph Theory - Matching Size

Replies
9
Views
547
Replies
1
Views
467
Replies
7
Views
864
Replies
6
Views
891
Replies
7
Views
780
Replies
2
Views
631
Back
Top