Does G with all its degrees at least three contain a cycle with a chord?

[MathematicalPhysicist]

Let G be a graph with all its degrees at least three.
Show that G contains a cycle with a chord (a chord is an edge which connects two non-adjacent vertices on the cycle).

I thought of proving this by induction on the number of vertices of G, but I am stuck.

Obviously, n>=4 otherwise it couldn't have all its degrees at least three.

So now I assume by induction that this assertion is true for every number smaller than n (untill 4), and I want to prove that this assertion is valid also for graph G with n vertices.

So if I build a new graph with taking out one vertex from G with its edges, I get a new graph, G' with n-1 vertices and it has vertices which are for sure at least have degrees two, if all of them have degree at least three then by the induction hypothesis I prove the assertion cause by adding the vertex I still have a cycle with a chord from the graph G', the problem of mine is when some of the vertices have degrees two.

Somehow I want to use a reduction that in the worse case scenraio I arrive at a case with 4 vertices and all of its degrees are at least three which guarantee a cycle with at least one chord.

Don't know how to show this?

Any hints?

 

[bpet]

Maybe a proof by contradiction involving a maximal chordless cycle, but still tricky to consider the cases where G has a bridge or a 2-edge cutset.

 

[MathematicalPhysicist]

Ok, I found a proof of this in Lovasz's textbook.

The proof goes as follows:
Let P=(x0,...,xm) be a maximal path in this graph, now because x0 has degree of at least three its other neighbours must be in this path or otherwise we can find another maximal path in contrary to our assumption.
so x0 for example has at least another two neighbours besides x1 on this path, say for 1<i<j<= m it has two neighbours xi and xj.
So the cycle (x0,...,xj) contains a chord namely (x0,xi).

Thank you, Lovasz!
:-)

 

[annie89]

i have many problems in geometry theory...please can anyone suggest me the best and experienced tutor for math.

http://fruition.com.au/"