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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Hm, thanks, that was indeed too trivial for me not to see. $\endgroup$ – Pavel Nov 21 '11 at 19:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.