1
$\begingroup$

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.

2 Answers 2

2

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.

0

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.