# Homework Help: Prove G contains a cycle of length at least k+1

1. Sep 29, 2010

### cxc001

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. Sep 29, 2010

### fzero

Consider one of the vertices, $$\nu_k$$ of degree $$k$$. Let the set of vertices which are connected to this one be $$\{ \nu_i^{(k)} \}$$. What is the minimum path length of a cycle $$C^{(k)}$$ that connects all of the $$\nu_i^{(k)}$$? Can you see a way to construct a cycle $$C'$$ of degree $$\text{deg}\, C^{(k)}+1$$?

3. Sep 29, 2010

### cxc001

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?

4. Sep 29, 2010

### Office_Shredder

Staff Emeritus
This is not likely to be true

5. Sep 29, 2010

### fzero

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.