1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Homework Help: Graph Theory - Matching Size

  1. Sep 30, 2013 #1
    1. The problem statement, all variables and given/known data

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

    2. Relevant equations

    n(G) = size of the vertex set of G and ∆(G)= maximum degree of v in G

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

    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?
  2. jcsd
  3. Sep 30, 2013 #2


    User Avatar
    Homework Helper

    I'm assuming by ##e(G)## you mean the number of edges in ##G##.

    Also, you stated this :

    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?
  4. Sep 30, 2013 #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.
  5. Sep 30, 2013 #4


    User Avatar
    Homework Helper

    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.
  6. Sep 30, 2013 #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...
  7. Sep 30, 2013 #6


    User Avatar
    Homework Helper

    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: Sep 30, 2013
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted