Having a hard time proving the following: Given a graph with $n \geq 4$ vertices and $ 2n-3 $ edges, I need to show there is a cycle with chord in graph.
What I tried to do, is prove by induction. The base case is $4$, which is pretty trivial. Then for an induction step I have $ n+1 $ vertices and $ 2n-1 $ edges. Next I've used the first part of the question (this is the second part) which is: "If all the vertices are of degree at least three, then there is a cycle with a chord in the graph". By negation, I get that there is at least one vertex of degree < 3.
And now, the problematic part - if the degree of this vertex is 2, then it's enough to delete it and it's edges, and we're back to induction case - $n$ vertices and $2n-3$ edges. Though, I have no idea what to do if the degree is 1.
Any clue will be appreciated.