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 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.)
Lema 1
Seja $e$ uma aresta em um grafo $G$. Se $G \dot -e$ é $3$-conexo, então $G$ também é.
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 Teorema, isso contradiz nossa suposição de que $G \dot -e$ é $3$-conexo.
$\square$
Lema 2
Todo grafo $G \neq K^4$ $3$-conexo tem uma aresta $e$ tal que $G \dot -e$ é outro grafo $3$-conexo.
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.
$\square$
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.
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.
$\square$
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.
Referências
- Reinhard Diestel. “Graph Theory” .5th Electronic Edition 2016, pp. 62-64. Acesso em 07/05/2023.