2
$\begingroup$

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 less than $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.

1 Answers 1

3

If you delete a vertex of degree $1$, you have a graph with $n$ vertices and $2n-2$ edges, so just delete a random edge and you are back to the case of interest.

  • 0
    Hm, thanks, that was indeed too trivial for me not to see.2011-11-21