## You are here

HomeThomassen's theorem on $3$-connected graphs

## Primary tabs

# Thomassen’s theorem on $3$-connected graphs

Every $3$-connected graph $G$ with more than 4 vertices has an edge $e$ such that $G/e$ 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)\geq 3$, our contracted vertex $v_{{xy}}$ has to be one of these two. So for every edge $e$, $G$ has a vertex $z\neq 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.

## Mathematics Subject Classification

05C40*no label found*

- Forums
- Planetary Bugs
- HS/Secondary
- University/Tertiary
- Graduate/Advanced
- Industry/Practice
- Research Topics
- LaTeX help
- Math Comptetitions
- Math History
- Math Humor
- PlanetMath Comments
- PlanetMath System Updates and News
- PlanetMath help
- PlanetMath.ORG
- Strategic Communications Development
- The Math Pub
- Testing messages (ignore)

- Other useful stuff
- Corrections