Tutte's Wheel Theorem/Lemma

From ProofWiki
Jump to navigation Jump to search

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.


Proof

Aiming for a contradiction, suppose for all $e \in E$, $G / e$ contains a vertex cut $S$ such that $\card S \le 2$.

Let $x, y \in V$ be endvertices of $e$.

Since $\map \kappa G \ge 3$, the contracted vertex $v_{x, y}$ of $G / e$ lies in $S$.

That is, $\exists z \in V: z \notin \set {x, y}$.

Let $S = \set {v_{x, y}, z}$.

Then $T = \set {x, y, z}$ is a vertex cut of $G$.

Thus, every vertex in $T$ has an edge to every component of $G' = G - T$.

Let $C = \struct {V', E'}$ be the smallest component of $G'$.

Let $\map {\Gamma_G} z$ be the neighborhood of $z$.

Let $u \in \map {\Gamma_G} z \cap V'$.

By assumption, $G / z u$ is again not $3$-connected.

Thus, there exists $w \in V$ such that $\set {w, z, u}$ is a vertex cut of $G$.

It also follows that every vertex in $\{w, z, u\}$ has an edge to every component of $G'' = G - \set {w, z, u}$.

Since $x, y$ are connected, there exists a component $D = \struct {V'', E''}$ of $G''$ such that $V'' \cap \set {x, y} = \O$.

Then:

$V'' \subseteq \map {\Gamma_G} z \cap V' = \O$

Hence $V'' \subsetneq V'$ by the choice of $D$, which contradicts the assumption that $C$ is the smallest component.

$\Box$