Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer

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|cite|improve this answer

Your Answer


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.