- #1
MathematicalPhysicist
Gold Member
- 4,699
- 372
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?
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?