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: Prove G contains a cycle of length at least k+1

  1. Sep 29, 2010 #1
    This is a graph theory related question.

    Let G be a simple graph with min. degree k, where k>=2. Prove that G contains a cycle of length at least k+1.

    Am I suppose to use induction to prove G has a path length at least k first, then try to prove that G has a cycle of length at least k+1? Or should I go directly use induction to prove G contains a cycle of length at least k+1???
     
  2. jcsd
  3. Sep 29, 2010 #2

    fzero

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Consider one of the vertices, [tex]\nu_k[/tex] of degree [tex]k[/tex]. Let the set of vertices which are connected to this one be [tex]\{ \nu_i^{(k)} \}[/tex]. What is the minimum path length of a cycle [tex]C^{(k)}[/tex] that connects all of the [tex]\nu_i^{(k)}[/tex]? Can you see a way to construct a cycle [tex]C'[/tex] of degree [tex]\text{deg}\, C^{(k)}+1[/tex]?
     
  4. Sep 29, 2010 #3
    Tell me if I'm not on the right track.

    Use induction on k.

    Pick a path P of maximum length, and suppose vertex vi is a vertex on this path, which has degree at least k, with a set of adjacent vertices {w1,w2,…,wj}, the adjacent vertex set must be on the path.
    The minimum path length of a cycle Ci that connected all of vertex set {w1,w2,…,wj } is k.
    Then extend the path to a cycle by adding the edge wjvi, so the resulting cycle has length at least k+1.
    We're done! Does this induction make sense?
     
  5. Sep 29, 2010 #4

    Office_Shredder

    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    This is not likely to be true
     
  6. Sep 29, 2010 #5

    fzero

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Your path P is too arbitrary and it's unlikely that you can prove very much given the constraints. However, it should be possible to argue that a simple graph contains a cycle that actually contains the vertex set wi and consider the path length of a closely related cycle that includes v.
     
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook