Thomassen’s theorem on $3$-connected graphs

Every $3$-connected (http://planetmath.org/KConnectedGraph) graph $G$ with morethan 4 vertices has an edge $e$ such that $G/e$ (http://planetmath.org/EdgeContraction) is also $3$-connected.

Note: $G/e$ denotes the graph obtained from $G$ by contracting the edge $e$.If $e=xy$ we also use the notation $G/xy$.

Suppose such an edge doesn’t exist. Then, for every edge $e=xy$, thegraph $G/e$ isn’t $3$-connected and can be made disconnected byremoving 2 vertices. Since $\kappa (G)\ge 3$, our contracted vertex$v_{xy}$ has to be one of these two. So for every edge $e$, $G$ has avertex $z\ne x,y$ such that $\{v_{xy},z\}$ separates $G/e$. Any 2vertices separated by $\{v_{xy},z\}$ in $G/e$ are separated in $G$ by$S:=\{x,y,z\}$. Since the minimal size of a separating set is 3, everyvertex in $S$ has an adjacent vertex in every component of $G-S$.

Now we choose the edge $e$, the vertex $z$ and the component $C$ suchthat $|C|$ is minimal. We also choose a vertex $v$ adjacent to $z$ in$C$.

By construction $G/zv$ is not $3$-connected since removing $xy$disconnects $C-v$ from $G/zv$. So there is a vertex $w$ such that$\{z,v,w\}$ separates $G$ and as above every vertex in $\{z,v,w\}$ hasan adjacent vertex in every component of $G-\{z,v,w\}$. We nowconsider a component $D$ of $G-\{z,v,w\}$ that doesn’t contain $x$ or$y$. Such a component exists since $x$ and $y$ belong to the samecomponent and $G-\{z,v,w\}$ isn’t connected. Any vertex adjacent to$v$ in $D$ is also an element of $C$ since $v$ is an element of$C$. This means $D$ is a proper subset of $C$ which contradicts ourassumption that $|C|$ was minimal.