# 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 |