grafos:estruct3connected [WikiMat]

==== A estrutura de grafos $3$-conexo: sem multigrafos ====

Agora nos voltamos para nosso segundo método de redução de grafos $3$-conexos para $K^4$, contraindo arestas. No que segue, consideramos apenas grafos, não multigrafos.

<WRAP round box 100%>
=== Lema 1 ===
//Todo grafo $3$-conexo $G \neq K^4$ tem uma aresta $e$ tal que $G/e$ é novamente $3$-conexo.//
</WRAP>

<WRAP round box 100%>
**//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$. 

{{ :grafos:graph300.png?450 |}}

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$.

<wrap right>$\square$</wrap>
</WRAP>

-----
<WRAP round box 100%>
=== 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.//
</WRAP>

<WRAP round box 100%>
**//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$. 

{{ :grafos:graph301.png?400 |}}

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$.

<wrap right>$\square$</wrap>
</WRAP>

-----

Assim como o [[grafos:estruct3connect#teorematutte_1966 |Teorema]], o Teorema acima nos permite construir todos os grafos $3$-conexos indutivamente a partir de $K^4$, por simples alterações locais e sem jamais sair da classe dos grafos $3$-conexos. Dado um grafo $3$-conexo já construído, escolha qualquer vértice $v$ e divida-o em dois vértices adjacentes $v',v''$. Em seguida, junte-os a todos os antigos vizinhos de $v$, cada um a pelo menos dois. Este é o núcleo essencial de um resultado de Tutte conhecido como **//Teorema da roda//**. ( Os grafos da forma $C^{n} * K^1$ são chamados de **rodas**; assim, $K^4$ é a menor roda.)

Para inteiros maiores $k$ não é mais verdade que em qualquer grafo $k$-conexo podemos contrair uma aresta de modo a obter outro grafo $k$-conexo. No entanto, para todo $k$ existe uma constante $n_{k}$ tal que em todo grafo $k$-conexo podemos excluir ou contrair uma aresta de modo que o grafo resultante não tenha separação de ordem menor que $k$ em que ambos os lados tenham pelo menos $n_{k}$ vértices.

-----

<WRAP round info>
=== Referências ===
  * Reinhard Diestel. [[https://www.math.uni-hamburg.de/home/diestel/books/graph.theory/preview/Ch3.pdf |“Graph Theory”]] .5th Electronic Edition 2016, pp. 64-65. Acesso em 07/05/2023.

</WRAP>