Every 3-connected graph has a cycle C such that G-V(C) is connected

441 Views Asked by At

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?

1

There are 1 best solutions below

2
On

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$.