Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
add comment

1 Answer

up vote 2 down vote accepted

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.

share|improve this answer
    
Hm, thanks, that was indeed too trivial for me not to see. –  Pavel Nov 21 '11 at 19:29
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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