Essa é uma revisão anterior do documento!
A estrutura de um grafo $3$-conexo a partir de um $K^4$
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.
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.
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.
O teorema 3.2.3 nos permite construir, recursivamente, toda a classe de grafos 3-conexos. A partir de K , 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 novo vértice de subdivisão.
Agora nos voltamos para nosso segundo método de redução de grafos 3-conexos para K, contraindo arestas. No que segue, consideramos apenas grafos, não multigrafos.
Lema 3.2.4.
Todo grafo 3-conexo G tem uma aresta E tal que G é novamente 3-conexo.
Dem.:
Suponha que não exista tal aresta E. Então, para cada aresta X o grafo G contém um separador S de no máximo 2 vértices. Como K, o vértice contraído V de G (consulte o capítulo 1.7) está em S e S, ou seja, G tem um vértice Z tal que V separa G. Então quaisquer dois vértices separados por V em G são separados em G por T. Como não subconjunto próprio de T separa G, cada vértice em T tem um vizinho em cada componente C de G.
Escolhemos a aresta X, 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 novamente não é 3-conexo, então novamente há um vértice Y tal que C separa G e, como antes, todo vértice em J tem um vizinho em cada componente de G.
(FIGURAAA
Como X e Y são adjacentes, G tem um componente D tal que D. Então todo vizinho de V em D está em C (desde C), então D e, portanto, D pela escolha de D. Isso contradiz a escolha de X, Z e C.
Teorema 3.2.5 (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.
Dem.:
Se G é 3-conexo, então pelo Lema 3.2.4 existe uma sequência G de grafos 3-conexos satisfazendo (i) e (ii).
Inversamente, e para mostrar o enunciado final do teorema , seja G uma sequência de grafos satisfazendo (i) e (ii); mostramos que se G é 3-conexo, G também é para todo I. Suponha que não, seja S um separador de no máximo 2 vértices em G e seja C dois componentes de G . Como X e Y são adjacentes, podemos supor que V. Então C não contém ambos os vértices X nem um vértice V: caso contrário, V ou V estariam separados de C em G por no máximo dois vértices, uma contradição. Mas agora C contém apenas um vértice: X ou Y. Isso contradiz nossa suposição de D.
Assim como o Teorema 3.2.3, o Teorema 3.2.5 nos permite construir todos os grafos 3-conexos indutivamente a partir de K, 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; 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 gráficos da forma C são chamados de rodas; assim, K é 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 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 vértices. Veja as notas.
Teo 3.2.6 (TUTTE 1963)
O espaço de ciclo de um grafo 3-conexo é gerado por seus ciclos induzidos não separados.
Dem.:
Seja G um grafo fixo 3-conexo, de ordem N digamos. Provamos que cada um de seus ciclos C é uma soma de ciclos induzidos não separados, aplicando indução em K, onde B denota a maior ordem de um componente de G se houver um, e B se V.
Não há ciclos C para os quais K, então a indução começa. Agora seja dado C para a etapa de indução. Se C é um ciclo de extensão, é a soma de dois ciclos C, onde E uma corda. Como K, estamos em casa por indução.
Suponha agora que G, e seja o maior componente de G. Suponha primeiro que
G contém um caminho C P tal que cada um dos dois caminhos U em C tem um vértice interno em N. (*) (FIGURAAAAA
Então C é a soma dos dois ciclos C contendo P, e para cada um destes C existe uma componente de G que contém B propriamente. Daí K , e estamos novamente em casa por indução.
Suponha finalmente que (*) falhe. Então cada vértice de C envia uma aresta para B. (De fato, se não, então C contém um N-caminho Q com T. Como G é 3-conexo, C, e há um caminho Q em G. Tal caminho P seria satisfaz (*).) Como V, qualquer acorde de C também seria um caminho P como em (*), então C não tem acorde. Portanto, a menos que o próprio C seja induzido e não separe, G tem um componente B. Seja P um caminho C através de B, e seja Q um caminho C-P em G. Observe que Q também evita B. Agora C contém três ciclos C somando a C e cada um perdendo um vértice de C. Como todo vértice de C envia uma aresta para B, portanto, temos K para cada K, completando a etapa de indução.