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

Thread: 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
    3,455
    Thanks
    1368

    Re: Graph theory matching size

    If there are no isolated vertices, then all vertices have degree at least 1. Hence, $\displaystyle e(G) \ge \dfrac{n(G)}{2}$. Now, $\displaystyle \Delta(G)$ is the maximum degree of any vertex. If $\displaystyle G$ has $\displaystyle k$ edges and $\displaystyle \Delta(G) = k$, then there exists a vertex incident to every edge in $\displaystyle G$. This would imply that $\displaystyle 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 $\displaystyle k$ edges. Let $\displaystyle G$ be a graph with $\displaystyle k$ edges, and let $\displaystyle H = G-e$ for some $\displaystyle e \in E(G)$. Now, by the IH, $\displaystyle H$ satisfies the hypothesis. Add back $\displaystyle e$. If the smallest integer greater than or equal to $\displaystyle \dfrac{n(G)}{1+\Delta(G)}$ equals the smallest integer greater than or equal to $\displaystyle \dfrac{n(H)}{1+\Delta(H)}$, then a matching in $\displaystyle H$ that satisfies the hypothesis is a matching in $\displaystyle G$ that satisfies the hypothesis. So, figure out when adding $\displaystyle e$ to $\displaystyle H$ will make that number increase. That will help you figure out what you need to prove. (Hint: $\displaystyle \Delta(G) \ge \Delta(H)$)
    Last edited by SlipEternal; Sep 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
    3,455
    Thanks
    1368

    Re: Graph theory matching size

    If $\displaystyle \Delta(G) \ge \Delta(H)$ and $\displaystyle n(G) = n(H)$ then $\displaystyle \dfrac{n(H)}{1+\Delta(H)} \ge \dfrac{n(H)}{1+\Delta(G)} = \dfrac{n(G)}{1+\Delta(G)}$. So, any matching of $\displaystyle H$ that satisfies the hypothesis will still be a matching in $\displaystyle 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
    3,455
    Thanks
    1368

    Re: Graph theory matching size

    (Oh, unless deleting $\displaystyle e$ from $\displaystyle G$ leaves an isolated vertex)... so, you need to be careful when picking $\displaystyle e$. If removing any $\displaystyle e$ will leave an isolated vertex, then you know something else about $\displaystyle 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: Oct 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: Dec 3rd 2010, 06:44 AM
  3. Replies: 1
    Last Post: Sep 26th 2010, 09:53 AM
  4. Replies: 0
    Last Post: Sep 25th 2010, 05:59 AM
  5. Graph Theory - Size of a Line Graph
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: Jul 25th 2010, 11:15 PM

Search Tags


/mathhelpforum @mathhelpforum