grafos:estruct3connect [WikiMat]

==== A estrutura de um grafo $3$-conexo a partir de um $K^4$: com multigrafos ====

Nesta seção, descrevemos como todo grafo $3$-conexo pode ser obtido de um $K^4$ por uma sucessão de operações elementares preservando a $3$-conexidade. Provamos então um teorema de Tutte sobre a estrutura algébrica do espaço cíclico de grafos $3$-conexos.

A [[grafos:2conexo#proposicao| Proposição]] descreve como os grafos $2$-conexos podem ser construídos indutivamente, partindo de um ciclo. Todos os grafos construídos no processo eram eles próprios $2$-conexos, então os grafos construíveis desta forma são precisamente os grafos $2$-conexos. Agora, vamos fazer algo parecido para grafos $3$-conexo. Vamos provar que todo grafo $G \neq K^4$ $3$-conexo pode ser transformado em um grafo $3$-conexo menor de duas maneiras: deletando uma aresta (e suprimindo quaisquer vértices de grau $2$ que possam surgir), e contraindo uma aresta. A inversão desses processos nos dará duas maneiras independentes de construir todos os grafos $3$-conexos a partir de um $K^4$.

Dada uma aresta $e$ em um grafo $G$, escrevamos $G \dot -e$ para o multigrafo obtido de $G-e$ suprimindo qualquer extremidade de $e$ que tenha grau $2$ em $G-e$. 

----

(Veja o Capítulo 1.10 para a definição formal de supressão de vértices em um multigrafo. Lembre-se também de que multigrafos 3-conexos não podem ter arestas múltiplas. Como as arestas paralelas que surgem quando um vértice é suprimido não são excluídas, nossa suposição no Lema 3.2.1 de que o multigrafo G é 3-conexo implica que nenhuma aresta paralela surge quando é formal do grafo G. Assim, G também está em fato um gráfico.)

----


<WRAP round box 100%>
=== Lema 1 ===
//Seja $e$ uma aresta em um grafo $G$. Se $G \dot -e$ é $3$-conexo, então $G$ também é.//
</WRAP>

<WRAP round box 100%>
**//Demonstração://**

Pensando em $G$ como obtido de $G \dot -e$ adicionando $e$, chamemos os vértices de $G \dot -e$ de vértices //antigos// de $G$, e qualquer outro vértice de $G$ (que será um fim de $e$) de novo vértice //novo//. Lembrando que $G \dot -e$, sendo $3$-conexo, não possui arestas paralelas, é fácil ver que, em $G$, não há dois vértices $x_1,x_2$ que possam separar um novo vértice de todos os vértices antigos. Portanto, basta mostrar que $\{x_1,x_2\}$ não pode separar dois vértices antigos. Se o fizessem, esses vértices antigos seriam separados em $G \dot -e$  por $x_1'$ e $x_2'$, onde $x_{i}' = x_{i}$  ou, se $x_{i}$ for novo, $x_{i}'$ é a aresta de $G \dot -e$ subdividida por $x_{i}$. Pelo [[.cicloDeltaKConexidade| Teorema]], isso contradiz nossa suposição de que $G \dot -e$ é $3$-conexo.

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

-----

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

<WRAP round box 100%>
**//Demonstração://**

Começamos mostrando que $G$ contém um $TK^4$. Seja $C$ um ciclo mais curto e $P = u \dot v$ um $C$-caminho em $G$. Então $\dot P \neq \emptyset$ desde que $C$ é induzido, então $G - \{u,v\}$ contém um caminho $C-P$ $\mathrm{Q}$. Agora $C \cup P \cup \mathrm{Q} = TK^4$.

Como $G \neq K^4$, existe um grafo $J \not \backsimeq G$ $3$-conexo tal que $G$ contém um $TJ$. Escolha $J$ com $||J||$ máximo, e então $H$ com $||H||$ máximo. Encontraremos uma aresta $e$ tal que $G \dot -e \backsimeq J$.

Claramente $H \neq G$. Seja $P =u \dots v$ um $H$-caminho em $G$, escolhido se possível de forma que $u$ e $v$ não estejam nas mesmas arestas (subdivididas) de $J$. $(*)$

Se $P$ não satisfaz $(*)$ então $H = J$; pois como $G$ é $3$-conexo, os vértices que subdividem uma aresta de $J$ poderiam ser unidos por um $H$-caminho a um vértice que não está na mesma aresta subdividida de $J$. Nossa suposição de que $P$ não satisfaz $(*)$,portanto implica que $uv \in E(J)=E(H)$. Uma vez que $G$ não possue arestas paralelas, $P$ tem um vértice interno. Agora $(H-uv) \cup P$ é outro $TJ$ com mais arestas que $H$, contrariando nossa escolha de $H$.

Portanto $P$ satisfaz $(*)$. Suprimindo quaisquer vértices de grau $2$ em $H \cup P$ obtemos um multigrafo $J'$ tal que $J' \dot -e =J$, onde $e$ é a aresta correspondente a $P$. Por $(*)$ a aresta $e$ não é paralela a uma aresta de $J$, então $J'$ é de fato um grafo. Pelo Lema $1$ acima, $J'$ é $3$-conexo. Logo, $J' \backsimeq G$ pela maximalidade de $J$, completando a prova.

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

----

<WRAP round box 100%>
=== Teorema: Tutte (1966) ===

//Um grafo $G$ é $3$-conexo se, e somente se,  existe uma sequência $G_0, \dots , G_{n}$ de grafos tais que//

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

$(ii)$ $G_{i+1}$ //possui uma aresta $e$ tal que $G_{i} = G_{i+1} - e$, 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, use o Lema $2$ acima para encontrar $G_{n} \dots , G_0$ sucessivamente. Reciprocamente, se $G_0 \dots G_{n}$ é qualquer sequência de grafos satisfazendo $(i)$ e $(ii)$, então todos esses grafos, e em particular $G = G_{n}$, são $3$-conexos pelo Lema $1$ acima.

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

----

O teorema logo acima nos permite construir, recursivamente, toda a classe de grafos $3$-conexos. A partir de $K^4$ , simplesmente adicionamos a cada grafo já construído uma nova aresta em todos os sentidos compatíveis com $(ii)$: entre dois vértices já existentes, entre novos vértices subdivididos inseridos (não na mesma aresta), ou entre um vértice antigo e um vértice novo de subdivisão.


----

<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. 62-64. Acesso em 07/05/2023.

</WRAP>