Results 1 to 5 of 5
Like Tree1Thanks
  • 1 Post By SlipEternal

Math Help - Graph theory matching size

  1. #1
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169

    Graph theory matching size

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

    I have started this problem several times, but this is my latest attempt:

    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?

    Thanks for any help.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: Graph theory matching size

    If there are no isolated vertices, then all vertices have degree at least 1. Hence, e(G) \ge \dfrac{n(G)}{2}. Now, \Delta(G) is the maximum degree of any vertex. If G has k edges and \Delta(G) = k, then there exists a vertex incident to every edge in G. This would imply that G has only one component. Why are you limiting to only connected graphs that also happen to be stars?

    Instead, assume the hypothesis holds for any graph with fewer than k edges. Let G be a graph with k edges, and let H = G-e for some e \in E(G). Now, by the IH, H satisfies the hypothesis. Add back e. If the smallest integer greater than or equal to \dfrac{n(G)}{1+\Delta(G)} equals the smallest integer greater than or equal to \dfrac{n(H)}{1+\Delta(H)}, then a matching in H that satisfies the hypothesis is a matching in G that satisfies the hypothesis. So, figure out when adding e to H will make that number increase. That will help you figure out what you need to prove. (Hint: \Delta(G) \ge \Delta(H))
    Last edited by SlipEternal; September 30th 2013 at 03:20 PM.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Member
    Joined
    Oct 2009
    From
    United States
    Posts
    169

    Re: Graph theory matching size

    The number will increase when you add e back to a vertex in H with the maximum degree. Is that what you're thinking?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: Graph theory matching size

    If \Delta(G) \ge \Delta(H) and n(G) = n(H) then \dfrac{n(H)}{1+\Delta(H)} \ge \dfrac{n(H)}{1+\Delta(G)} = \dfrac{n(G)}{1+\Delta(G)}. So, any matching of H that satisfies the hypothesis will still be a matching in G that will satisfy the hypothesis.
    Thanks from tarheelborn
    Follow Math Help Forum on Facebook and Google+

  5. #5
    MHF Contributor
    Joined
    Nov 2010
    Posts
    1,407
    Thanks
    523

    Re: Graph theory matching size

    (Oh, unless deleting e from G leaves an isolated vertex)... so, you need to be careful when picking e. If removing any e will leave an isolated vertex, then you know something else about G, and you can still show that the graph satisfies the hypothesis.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. maximum matching and size
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 5th 2011, 02:04 PM
  2. How do you show a graph has a complete matching?
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: December 3rd 2010, 06:44 AM
  3. Replies: 1
    Last Post: September 26th 2010, 09:53 AM
  4. Replies: 0
    Last Post: September 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: July 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum