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/"

 

[blue_raver22]

One possible approach to this problem could be to use the fact that a graph with all degrees at least three must be connected. This means that there is a path between any two vertices in the graph.

Using this information, we can start by choosing any two non-adjacent vertices and finding a path between them. Since all degrees are at least three, this path must contain at least three vertices.

Next, we can consider the vertices on this path and their adjacent vertices. Since all degrees are at least three, there must be at least one vertex with degree three or higher on this path. This vertex, along with its adjacent vertices, forms a cycle with a chord.

If this cycle does not include all the vertices on the original path, we can repeat this process with a different pair of non-adjacent vertices until we find a cycle with a chord that includes all the vertices on the original path.

Therefore, we have shown that a graph with all degrees at least three must contain a cycle with a chord. This proof works for any number of vertices, making it applicable to the induction step in your approach.