Thomassen’s theorem on $3$-connected graphs

Every $3$-connected (http://planetmath.org/KConnectedGraph) graph $G$ with more than 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$, the graph $G/e$ isn’t $3$-connected and can be made disconnected by removing 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 a vertex $z\ne x,y$ such that $\{v_{xy},z\}$ separates $G/e$. Any 2 vertices 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, every vertex 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$ such that $|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\}$ has an adjacent vertex in every component of $G-\{z,v,w\}$. We now consider 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 same component 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 our assumption that $|C|$ was minimal.

Title	Thomassen’s theorem on $3$-connected graphs
Canonical name	ThomassensTheoremOn3connectedGraphs
Date of creation	2013-03-22 13:11:09
Last modified on	2013-03-22 13:11:09
Owner	Mathprof (13753)
Last modified by	Mathprof (13753)
Numerical id	6
Author	Mathprof (13753)
Entry type	Theorem
Classification	msc 05C40
Related topic	EdgeContraction