Lema 1

Todo grafo $3$-conexo $G \neq K^4$ tem uma aresta $e$ tal que $G/e$ é novamente $3$-conexo.

Demonstração:

Suponha que não exista tal aresta $e$. Então, para cada aresta $xy \in G$, o grafo $G/xy$ contém um separador $S$ de no máximo $2$ vértices. Como $\kappa (G) \geq 3$, o vértice contraído $v_{xy}$ de $G/xy$ está em $S$ e $|S| =2$, ou seja, $G$ tem um vértice $z \notin \{x,y\}$ tal que $\{v_{xy},z\}$ separa $G/xy$. Então quaisquer dois vértices separados por $\{v_{xy},z\}$ em $G/xy$ são separados em $G$ por $T := \{x,y,z\}$. Como nenhum subconjunto próprio de $T$ separa $G$, cada vértice em $T$ tem um vizinho em cada componente $C$ de $G-T$.

Escolhemos a aresta $xy$, o vértice $z$ e a componente $C$ de modo que $|C|$ seja o menor possível, e escolhemos um vizinho $v$ de $z$ em $C$.

Por suposição, $G/zv$ novamente não é $3$-conexo, então novamente há um vértice $w$ tal que $\{z,v,w\}$ separa $G$ e, como antes, todo vértice em $\{z,v,w\}$ tem um vizinho em cada componente de $G-\{z,v,w\}$.

Como $x$ e $y$ são adjacentes, $G-\{z,v,w\}$ tem um componente $D$ tal que $D \cap \{x,y\} = \emptyset$. Então todo vizinho de $v$ em $D$ está em $C$ (desde que $v \in C$), então $D \cap C = \emptyset$ e, portanto, $D \subsetneq C$ pela escolha de $D$. Isso contradiz a escolha de $xy,z$ e $C$.

$\square$

Teorema: Tutte(1961)

Um grafo $G$ é $3$-conexo se, e somente se, existe uma sequência $G_0, \dots ,G_{n}$ de grafos com as duas seguintes propriedades:

$(i)$ $G_0 = K^4$ e $G_{n} = G$;

$(ii)$ $G_{i+1}$ possui uma aresta $xy$ tal que $d(x),d(y) \geq 3$ e $G_{i} = G_{i+1}/xy$, para todo $i<n$.

Além disso, os grafos de qualquer uma dessas sequências são todos $3$-conexos.

Demonstração:

Se $G$ é $3$-conexo, então pelo Lema $1$ acima existe uma sequência $G_{n}, \dots, G_0$ de grafos $3$-conexos satisfazendo $(i)$ e $(ii)$.

Inversamente, e para mostrar o enunciado final do teorema , seja $G_0, \dots G_{n}$ uma sequência de grafos satisfazendo $(i)$ e $(ii)$; mostramos que se $G_{i}$ é $3$-conexo, $G_{i+1}$ também é para todo $i<n$. Suponha que não, seja $S$ um separador de no máximo $2$ vértices em $G_{i+1}$, e seja $C_1,C_2$ duas componentes de $G_{i+1}-S$ . Como $x$ e $y$ são adjacentes, podemos supor que $\{x,y\} \cap V(C_1) = \emptyset$.

Então $C_2$ não contém ambos os vértices $x,y$ nem um vértice $v \notin \{x,y\}$: caso contrário, $v_{xy}$ ou $v$ estariam separados de $C_1$ em $G_{i}$ por no máximo dois vértices, uma contradição. Mas agora $C_2$ contém apenas um vértice: $x$ ou $y$. Isso contradiz nossa suposição de que $d(x),d(y) \geq 3$.

$\square$