Tutte's Wheel Theorem

This article needs to be linked to other articles. You can help $\mathsf{Pr} \infty \mathsf{fWiki}$ by adding these links. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{MissingLinks}} from the code.

This article needs to be tidied. Please fix formatting and $\LaTeX$ errors and inconsistencies. It may also need to be brought up to our standard house style. To discuss this page in more detail, feel free to use the talk page. When this work has been completed, you may remove this instance of {{Tidy}} from the code.

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.