# Tutte's Wheel Theorem

## Theorem

Every $3$-connected graph can be obtained by the following procedure:

• Start with $G_0 := K_4$
• Given $G_i$ pick a vertex $v$
• Split into $v'$ and $v''$ and add edge $\set {v', v''}$

This procedure directly follows from the theorem:

A graph $G$ is $3$-connected (A) if and only if there exists a sequence $G_0, G_1, . . . , G_n$ of graphs with the following properties (B):
• $G_0 = K_4$ and $G_n = G$;
• $G_{i + 1}$ has an edge $e = x y$ with $\map \deg x, \map \deg y \ge 3$ and $G_i = G_{i + 1} / e$ for every $i < n$.

## Proof

### A $\implies$ B

Directly follows from Tutte's Wheel Theorem/Lemma.

### B $\implies$ A

If $G_i$ is $3$-connected then so is $G_{i + 1}$ for every $i < n$.

Suppose not. Then $G_i = G_{i + 1} / e$ where $G_{i + 1}$ is $2$-connected.

Let $S$ be a vertex cut such that $\card S \le 2$, and $C_1, C_2$ be two components of $G_{i + 1} - S$.

Since $x, y$ are connected, we can assume $\map V {C_1} \cap \set {x, y} = \O$.

Then, $C_2$ cannot contain both $x$ and $y$ nor it can contain any $v \notin \set {x, y}$.

(otherwise $v$ or $u_{x y}$ would be separated from $C_1$ in $G_i$ by at most two vertices.)

But now $C_2$ contains only one vertex: either $x$ or $y$.

This contradicts $\map \deg x, \map \deg y \ge 3$.

$\blacksquare$

## Source of Name

This entry was named for William Thomas Tutte.