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