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.

Let $v_1$, $v_2$, and $v_3$ be distinct vertices of a graph $G$ such that $G\setminus\{v_1\}$, $G\setminus\{v_2\}$ and $G\setminus\{v_3\}$ are all acyclic. Then prove that $G$ contains a maximum of one cycle.

A hint would be greatly appreciated.

share|improve this question
    
If this is homework, that's OK, but then you should add the "homework" tag. –  Gerry Myerson Sep 30 '12 at 4:22
    
Sorry, added. :) –  Heisenberg Sep 30 '12 at 4:23
add comment

2 Answers

up vote 2 down vote accepted

Show the hypothesis implies every cycle goes through all three of the vertices $v_1.v_2,v_3$. Then show that if there are two or more such cycles then there are two ways to get from one of the three vertices to another, so removing the third vertex leaves a cycle intact.

That's more of an outline than a hint, but I think it still leaves some work to be done in fleshing it out. If it's right, that is.

share|improve this answer
add comment

It wasn't stated that $v_1$, $v_2$, and $v_3$ are distinct, but without this the claim is false, so we assume it.

For purposes of contradiction, assume $G$ has two cycles, $C_1$ and $C_2$. Then $v_1$, $v_2$ and $v_3$ must be contained on both. WLOG, suppose the path $v_1 - v_2 - v_3$ is contained both on both $C_1$ and $C_2$. But then removing $v_2$ does not make $G$ acyclic since a cycle remains.

I'll leave it to you to fill in the details. A picture probably helps.

share|improve this answer
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.