Tutte's Wheel Theorem/Lemma

From ProofWiki
Jump to navigation Jump to search

Lemma

If a graph $G$ is 3-connected with $|V\left({G}\right)| > 4$ then $\exists e, \: e \in E\left({G}\right)$ such that $G \thinspace / \thinspace e$ is also 3-connected.


Proof

Suppose that no such edge $e$ exists.

Then $\forall e, \: e = xy \in E\left({G}\right)$, $\: G \thinspace / \thinspace e$ contains a vertex cut $S, \: |S| ≤ 2$.

Since $\kappa\left({G}\right) \geq 3$, the contracted vertex $v_{x,y}$ of $G \thinspace / \thinspace e$ lies in $S$ (i.e. $\exists z, \: z \in G, \: z \notin \{x,y\}$.)

Let $S = \{v_{x,y}, z\}$. Then $T = \{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$ be the smallest component of $G'$.

Let $u \in N\left({z}\right) \cap C$ where $N\left({z}\right)$ is the set of all neighbours of the vertex $z$.

By assumption, $G \thinspace / \thinspace zu$ is again not 3-connected, so again $\exists w$ such that $\{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 - \{w, z, u\}$.

Since $x,y$ are connected, $\exists D$, $D$ is a component of $G''$ and $D \cap \{x,y\} = \emptyset$.

Then, $D \subseteq N\left({z}\right) \cap V\left({C}\right) = \emptyset$.

Hence $D \varsubsetneqq C$ by the choice of $D$, which contradicts the assumption that $C$ was the smallest component.

$\Box$