Return to Revisions

Here is a quick reduction. Hopefully someone else can finish it off. Since $G$ is 2-connected, it has an ear-decomposition starting with the cycle $C$. Next, when building the ear-decomposition, for as long as possible always choose ears $P$ such that both ends of $P$ are in $C$ and $P$ has two edges. Now consider the last ear $P'$. If $P'$ is just an edge $e$, then $G \setminus e$ is 2-connected and we win by induction. Thus, $P$ has at least two edges. If $P$ has at least 3 edges, then let $G'$ be the graph obtained from $G$ by replacing $P$ by a path of length 2. Note that $G'$ is 2-connected, and every vertex in $C$ still has a neighbour outside of $C$ in $G'$. Thus, by induction, $G'$ and hence $G$ has a cycle longer than $C$. Thus, $P$ has exactly two edges. If at least one end of $P$ is not in $C$, then by replacing $P$ with a single edge, we win by induction. Thus, both ends of $P$ are in $C$. Therefore, every ear is a $C$-path with two edges. We can thus colour the edges of $C$ red and replace each ear with a blue edge. We now have a graph $G''$ with $V(G'')=V(C)$, and where every vertex is incident to a blue edge. I think it should be easy to show that such a graph has a cycle longer than $C$ (red edges have length 1, and blue edges have length 2).