I'm currently working on an exercise which asks me to prove the following statement:
Prove that every 3-connected simple graph G has a cycle C such that G − V (C) is connected.
I've been told to attempt a proof by contradiction by considering a cycle C with a largest component of G-V(C). I'm having some trouble figuring out how to start. Could someone point me in the right direction?
The hint makes sense.
Suppose such a cycle does not exist, and let $C$ be a cycle that makes the largest component of $G-V(C)$ as large as possible. Let $A$ be a largest component of $G-V(C)$, $B$ another component. Let $w$ be a vertex on $C$ that has a neighbor $a$ in $A$ (such vertex must exist!).
Take $b\in B$. Because $G$ is 3-connected there is a 3-fan from $b$ to $C$. Assume the fan hits $C$ in $v_1,v_2,v_3$. We may assume that $v_1$ and $v_2$ are both different from $w$. Let $P_1$ be the $b,v_1$-path of the fan and $P_2$ the $b,v_2$-path.
Walk from $v_1$ to $v_2$ around $C$ in such a way that you avoid $w$ and complete this path with $P_1$ and $P_2$ to form a new cycle $C'$.
Now note that the component of $G-V(C')$ containing $a$ still contains everything of $A$, and also $w$, contradicting the choice of $C$.