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.

This page has been identified as a candidate for refactoring. In particular: Separate the theorem from the algorithm it justifies Until this has been finished, please leave {{Refactor}} in the code. New contributors: Refactoring is a task which is expected to be undertaken by experienced editors only. Because of the underlying complexity of the work needed, it is recommended that you do not embark on a refactoring task until you have become familiar with the structural nature of pages of $\mathsf{Pr} \infty \mathsf{fWiki}$. 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 {{Refactor}} 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, \dotsc, 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

Lemma

Let $G = \struct {V, E}$ be a $3$-connected graph such that $\card V > 4$.

Then there exists $e \in E$ such that $G / e$ is also $3$-connected.

$\Box$

A $\implies$ B

Directly follows from the 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.