Você já tentou conectar três casas a três fontes de utilidade — gás, água e eletricidade — usando linhas que não se cruzam? Se sim, descobriu empiricamente um resultado matemático profundo: essa tarefa é impossível.
O ramo da teoria dos grafos que estuda quando conexões podem ser feitas sem cruzamentos chama-se teoria da planaridade. Ela tem consequências práticas importantes no design de circuitos impressos e na visualização de redes.
Por que Grafos Planares Importam? #
Saber se um grafo pode ser desenhado sem cruzamentos não é só curiosidade geométrica — é uma pergunta com peso prático em ciência da computação e engenharia:
- Design de circuitos impressos (PCB) e VLSI: uma trilha de cobre que cruza outra na mesma camada causa curto-circuito. Determinar se um circuito é planar decide se ele cabe em uma única camada ou exige vias e camadas extras.
- Visualização de redes: diagramas de dependências de software, mapas de redes sociais e fluxogramas ficam muito mais legíveis quando desenhados sem cruzamentos — algoritmos de graph drawing usam testes de planaridade como primeiro passo.
- Mapas e o Teorema das Quatro Cores: todo mapa político pode ser representado por um grafo planar (cada região vira um vértice, cada fronteira compartilhada vira uma aresta) — é essa planaridade que torna o famoso Teorema das Quatro Cores um problema sobre grafos, tratado na seção de coloração deste artigo.
- Redes de transporte e utilidades: o problema das três casas e três utilidades, a seguir, não é um enigma isolado — decidir se uma rede de tubulações, cabos ou trilhos pode ser instalada sem cruzamentos é literalmente esse mesmo problema.
O Problema das Três Casas e Três Utilidades #
O enigma clássico pede para conectar 3 casas (\(h_1, h_2, h_3\)) a 3 fontes de utilidade (gás \(g\), água \(w\), eletricidade \(e\)), por exemplo por razões de segurança, sem que nenhuma das 9 linhas de conexão se cruze. Tente desenhar 8 das conexões sem cruzamentos — é fácil. Agora tente adicionar a última, entre a casa que sobrou e a utilidade que sobrou: não importa como você reorganize o desenho, essa última linha sempre vai cruzar alguma das outras oito.
Podemos modelar esse problema como um grafo, com um vértice para cada casa e cada utilidade, e uma aresta para cada uma das 9 conexões. A figura a seguir mostra duas representações desse grafo: \(G_1\), com as 3 casas de um lado e as 3 utilidades do outro (o desenho “bipartido” natural do enunciado), e \(G_2\), com os mesmos 6 vértices dispostos em um hexágono, alternando casas e utilidades. Os dois desenhos parecem diferentes, mas \(G_1\) e \(G_2\) são isomorfos — são o mesmo grafo, apenas desenhados de formas distintas.
Esse grafo é um grafo bipartido completo: cada casa está ligada a todas as 3 utilidades, e vice-versa. Ele é denotado por \(K_{3,3}\).
Matematicamente, o problema das três casas e três utilidades equivale então a perguntar: é possível desenhar o grafo \(K_{3,3}\) de modo que nenhuma aresta cruze outra? Ou seja, o grafo bipartido completo \(K_{3,3}\) é planar? A resposta — que provaremos rigorosamente mais adiante — é não.
Grafos Planares #
Um grafo \(G\) é planar se pode ser desenhado no plano sem que qualquer par de arestas se cruze, exceto nos vértices. Tal desenho é chamado de representação plana (ou embedding plano) de \(G\) (veja o verbete Planar graph).
Exemplo 1: o grafo completo \(K_4\)
Enunciado: O desenho mais óbvio de \(K_4\) — um quadrado com as duas diagonais — tem cruzamento de arestas. Isso significa que \(K_4\) é não planar?
Solução: Não. A figura mostra essa representação não plana ao lado de três representações planas equivalentes do mesmo grafo \(K_4\), todas sem cruzamento de arestas — basta reorganizar os vértices. Logo, \(K_4\) é planar: existe pelo menos uma representação plana dele, mesmo que outros desenhos do mesmo grafo tenham cruzamentos.
Exemplo 2: os grafos \(K_5\) e \(K_{3,3}\)
Enunciado: É possível desenhar uma representação plana dos grafos \(K_5\) (grafo completo de 5 vértices) e \(K_{3,3}\) (o grafo do problema das utilidades, da seção anterior)?
Solução: Não. Por mais que você reposicione os vértices, sempre sobra pelo menos um cruzamento — a figura a seguir mostra os dois grafos desenhados dessa forma:
Vamos provar rigorosamente mais adiante, usando a Fórmula de Euler, que nenhum dos dois admite representação plana.
Outros exemplos imediatos:
- Árvores: sempre planares — dá para desenhá-las sem cruzamentos a partir de uma raiz, nível a nível, com os filhos de cada vértice lado a lado logo abaixo dele
- \(C_n\) (ciclos): planar para todo \(n\)
Faces de um Grafo Planar #
Quando desenhamos um grafo planar no plano, as arestas dividem o plano em regiões chamadas faces.
Se \(G\) é um grafo planar, toda representação plana de \(G\) divide o plano em regiões chamadas faces. Uma dessas regiões é não limitada e é chamada de face externa.
Propriedade importante: Se \(G\) é um grafo planar, toda representação plana de \(G\) tem o mesmo número de faces, denotado por \(f\). Ou seja, embora o desenho de um grafo planar não seja único, o número de faces é uma invariante do grafo — não importa como você o desenhe, o número de regiões criadas é sempre o mesmo.
Exemplo: três representações do \(K_4\), sempre com 4 faces
Enunciado: Considere \(K_4\) (\(n = 4\) vértices, \(m = 6\) arestas) e três representações planas diferentes: \(R_1\), um triângulo externo com um vértice interno ligado aos três cantos; \(R_2\), um quadrado com uma diagonal e um arco externo; \(R_3\), quatro vértices em linha com arestas em arco por cima e por baixo. As três têm o mesmo número de faces?
Solução: Sim. Apesar de serem desenhos completamente diferentes do mesmo grafo, as três representações têm exatamente \(f = 4\) faces — em \(R_1\), por exemplo, são 3 faces internas (triangulares) mais 1 face externa. Essa coincidência não é acaso: é exatamente o que a Fórmula de Euler, a seguir, formaliza.
A Fórmula de Euler #
Se \(G\) é um grafo conexo e planar com \(n\) vértices, \(m\) arestas e \(f\) faces, então:
$$n - m + f = 2$$Prova:
Considere uma árvore geradora \(T\) de \(G\) (removendo \(m - (n-1)\) arestas):
- \(T\) tem \(n\) vértices, \(n-1\) arestas, 1 face (todo o plano): \(n - (n-1) + 1 = 2\). ✓
Agora, adicionamos uma aresta de volta ao grafo. Cada aresta adicionada liga dois vértices que já estão no desenho e cria exatamente uma nova face (divide uma face existente em duas):
- \(\Delta n = 0\), \(\Delta m = +1\), \(\Delta f = +1\)
- A equação \(n - m + f = 2\) se mantém
Adicionando todas as \(m - (n-1)\) arestas restantes, chegamos a \(G\) com a igualdade preservada. Portanto, \(n - m + f = 2\) para todo grafo conexo e planar, que é o que queríamos demonstrar. \(\blacksquare\)
A fórmula é o caso plano de um invariante mais geral da topologia, a característica de Euler.
Exemplo: construindo o grafo a partir da árvore geradora
Enunciado: Como fica, passo a passo, a construção usada na prova acima — partir de uma árvore geradora \(T_G\) de um grafo \(G\) e devolver as arestas que faltam, uma a uma?
Solução: A figura a seguir ilustra a sequência: \(T_G\) tem apenas 1 face, o plano inteiro. A cada aresta devolvida, ela liga dois vértices que já existem no desenho e corta uma face existente em duas: por isso \(n\) fica fixo enquanto \(m\) e \(f\) aumentam juntos, sempre 1 a 1, preservando \(n - m + f = 2\) em cada etapa.
Verificação com \(K_4\)
\(n = 4\), \(m = 6\): \(4 - 6 + f = 2 \implies f = 4\). Confirmado! ✓
Se \(G\) é planar com \(c\) componentes conexos (o \(\omega(G)\) do artigo sobre caminhos), a fórmula vira \(n - m + f = 1 + c\). Aplicando a Fórmula de Euler a cada componente e somando, obtemos \(n - m + (\text{soma das faces}) = 2c\); mas a face externa foi contada \(c\) vezes, uma por componente, e é uma só. Tirando as \(c - 1\) repetições, \(n - m + f = 2c - (c - 1) = 1 + c\). Com \(c = 1\), volta-se a \(n - m + f = 2\).
Corolários: Limitantes para Grafos Planares #
A Fórmula de Euler implica desigualdades importantes que limitam o número de arestas em grafos planares.
Corolário 1 — Limite Geral #
Se \(G\) é conexo, planar e \(n \geq 3\), então:
$$m \leq 3n - 6$$Prova: Cada face é bordejada por pelo menos 3 arestas. Cada aresta borda no máximo 2 faces. Logo:
$$3f \leq 2m \implies f \leq \frac{2m}{3}$$Da Fórmula de Euler: \(f = 2 - n + m\). Substituindo:
$$3(2 - n + m) \leq 2m \implies 6 - 3n + 3m \leq 2m \implies m \leq 3n - 6$$Portanto, todo grafo conexo e planar com \(n \geq 3\) vértices tem \(m \leq 3n - 6\), que é o que queríamos demonstrar. \(\blacksquare\)
Corolário 2 — Grafos sem Triângulos #
Se \(G\) é conexo, planar, \(n \geq 3\) e sem triângulos (sem ciclos de comprimento 3), então:
$$m \leq 2n - 4$$Prova: Sem triângulos, cada face é bordejada por pelo menos 4 arestas. Logo:
$$4f \leq 2m \implies 4(2-n+m) \leq 2m \implies m \leq 2n - 4$$Portanto, todo grafo conexo e planar sem triângulos, com \(n \geq 3\) vértices, tem \(m \leq 2n - 4\), que é o que queríamos demonstrar. \(\blacksquare\)
Corolário 3 — \(K_5\) Não É Planar #
\(K_5\) tem \(n = 5\), \(m = 10\). Se fosse planar: \(m \leq 3(5) - 6 = 9\). Mas \(10 > 9\). Contradição. Portanto, \(K_5\) não é planar, que é o que queríamos demonstrar. \(\blacksquare\)
Corolário 4 — \(K_{3,3}\) Não É Planar #
\(K_{3,3}\) tem \(n = 6\) vértices, \(m = 9\) arestas, e é bipartido — não contém triângulos.
Suponha que \(K_{3,3}\) seja planar e tentemos aplicar o Corolário 1 primeiro: a relação exige \(m \leq 3n - 6\). Mas \(m = 9 < 3(6) - 6 = 12\) — a desigualdade é satisfeita, então o Corolário 1 sozinho não permite concluir nada sobre a planaridade de \(K_{3,3}\).
Como \(K_{3,3}\) não tem triângulos, podemos aplicar o Corolário 2, que é mais restritivo: a relação exige \(m \leq 2n - 4\). Mas \(m = 9 > 2(6) - 4 = 8\). Contradição.
Portanto, \(K_{3,3}\) não é planar, que é o que queríamos demonstrar. \(\blacksquare\)
As desigualdades \(m \leq 3n - 6\) e \(m \leq 2n - 4\) são necessárias para planaridade, mas não suficientes. Existem grafos que satisfazem essas restrições e ainda assim não são planares — foi justamente o que aconteceu acima com \(K_{3,3}\) e o Corolário 1.
Grafos que Contêm \(K_5\) ou \(K_{3,3}\) como Subgrafo #
Duas observações simples, mas úteis, decorrem de tudo o que vimos até aqui.
Observação 1: \(K_5\) e \(K_{3,3}\) são, respectivamente, os grafos não planares com o menor número de vértices e o menor número de arestas possíveis — mínimos provados, e não apenas os menores conhecidos. Como veremos com o Teorema de Kuratowski, todo grafo não planar contém uma subdivisão de um dos dois e, portanto, tem pelo menos 5 vértices e pelo menos 9 arestas.
Observação 2: Se \(G\) é um grafo planar, então todo subgrafo de \(G\) também é planar — remover vértices ou arestas de um desenho sem cruzamentos não pode criar um cruzamento. De forma equivalente:
Se um grafo \(G\) contém um grafo não planar como subgrafo, então \(G\) é não planar.
Essa observação já é suficiente para detectar não planaridade em grafos bem maiores do que \(K_5\) ou \(K_{3,3}\): basta encontrar uma dessas duas estruturas “escondida” dentro de um grafo maior.
Exemplo: dois grafos não planares por conterem \(K_5\) e \(K_{3,3}\)
Enunciado: Considere dois grafos \(G_1\) e \(G_2\):
- \(G_1\) é formado por uma cópia de \(K_5\) (destacada) com um vértice e uma aresta extras pendurados em um dos vértices.
- \(G_2\) é formado por uma cópia de \(K_{3,3}\) (destacada) com dois vértices extras pendurados.
\(G_1\) e \(G_2\) são planares?
Solução: Não, nenhum dos dois. Como \(G_1\) contém \(K_5\) como subgrafo, \(G_1\) não é planar. Como \(G_2\) contém \(K_{3,3}\) como subgrafo, \(G_2\) não é planar. Note que, neste exemplo, o grafo proibido aparece diretamente como subgrafo, sem qualquer subdivisão. A próxima seção generaliza essa ideia para quando o grafo proibido aparece “disfarçado” por subdivisões.
Subdivisão de Grafos #
Uma subdivisão de \(G\) é obtida inserindo vértices de grau 2 nas arestas de \(G\) — cada aresta pode ser substituída por um caminho de comprimento arbitrário.
Intuitivamente, subdividir uma aresta significa colocar um ou mais “pontos de passagem” intermediários nela, sem alterar a estrutura de conexões do grafo. A figura a seguir mostra um grafo \(G\) e uma subdivisão \(G’\) sua, com vértices de grau 2 (em vermelho) inseridos em quantidades variáveis em cada aresta.
Observação 3: Se \(G\) é planar, então qualquer subdivisão de \(G\) também é planar — inserir um vértice no meio de uma aresta não pode criar um cruzamento. De forma equivalente:
Se \(G\) é uma subdivisão de um grafo não planar, então \(G\) é não planar.
A figura a seguir ilustra essa observação com subdivisões do \(K_5\) e do \(K_{3,3}\), com os vértices de grau 2 inseridos destacados em vermelho:
Combinando a Observação 2’ (subgrafo, da seção anterior) com a Observação 3' (subdivisão), obtemos o resultado mais geral:
Observação 4: Se \(G\) é um grafo que contém uma subdivisão de \(K_5\) ou de \(K_{3,3}\) como subgrafo, então \(G\) é não planar.
O Teorema de Kuratowski #
O resultado mais profundo sobre grafos planares fornece uma caracterização completa:
Um grafo \(G\) é planar se e somente se não contém nenhuma subdivisão de \(K_5\) nem de \(K_{3,3}\) como subgrafo (veja o verbete Kuratowski’s theorem).
A direção “se \(G\) contém uma subdivisão de \(K_5\) ou \(K_{3,3}\), então \(G\) não é planar” já está provada — é exatamente a Observação 4 da seção anterior. A parte difícil e surpreendente do teorema é a recíproca: todo grafo que não contém essas subdivisões é necessariamente planar. Essa direção exige uma prova longa e técnica, que está fora do escopo deste artigo.
Este teorema é extraordinário: ele diz que \(K_5\) e \(K_{3,3}\) são, em algum sentido, os únicos obstáculos à planaridade. Todo grafo não planar contém um desses dois grafos “escondido” (possivelmente com subdivisões).
Embora o teorema forneça a caracterização teórica completa, verificar
computacionalmente se um grafo é planar levou ao desenvolvimento de algoritmos
sofisticados. O primeiro algoritmo de tempo linear, \(O(n)\), foi publicado por
John Hopcroft e Robert Tarjan em 1974; em 2004, John Boyer e Wendy Myrvold chegaram
a um algoritmo linear mais simples, que também constrói o desenho plano (veja o
verbete Planarity testing). No
networkx, um teste linear está pronto em nx.check_planarity.
Coloração de Grafos Planares #
No primeiro artigo da série, o Teorema das Quatro Cores apareceu como uma afirmação sobre mapas. Com a linguagem deste artigo, ele vira um teorema sobre grafos planares — e a Fórmula de Euler é suficiente para provar uma versão mais fraca dele.
Uma coloração de um grafo \(G\) com \(k\) cores atribui a cada vértice uma de \(k\) cores, de modo que vértices adjacentes recebam cores diferentes. O número cromático \(\chi(G)\) é o menor \(k\) para o qual existe uma coloração de \(G\) com \(k\) cores.
Algumas consequências imediatas da definição:
- Os vértices de uma mesma cor não podem ser vizinhos: formam um conjunto independente. Colorir \(G\) com \(k\) cores é dividir \(V(G)\) em \(k\) conjuntos independentes.
- Se \(G\) contém uma clique com \(k\) vértices, então \(\chi(G) \geq k\), porque os vértices da clique precisam de cores todas diferentes. Em particular, \(\chi(K_n) = n\).
- Um grafo com pelo menos uma aresta tem \(\chi(G) = 2\) exatamente quando é bipartido — as duas cores são os dois lados da bipartição. Por isso um ciclo ímpar precisa de 3 cores.
Dos mapas aos grafos planares. Cada região de um mapa vira um vértice, e duas regiões com uma fronteira comum de comprimento positivo viram vértices adjacentes. O grafo obtido é planar: basta pôr cada vértice dentro da sua região e ligar duas regiões vizinhas por uma linha que atravessa a fronteira comum. Colorir o mapa é colorir esse grafo, e o teorema ganha a sua forma em teoria dos grafos:
Todo grafo planar \(G\) tem \(\chi(G) \leq 4\).
Em 1879, Alfred Kempe publicou uma prova que foi aceita por mais de dez anos, até que Percy Heawood encontrou um erro nela, em 1890 — e, no mesmo trabalho, provou que cinco cores sempre bastam. A prova de Kenneth Appel e Wolfgang Haken, de 1976, reduziu o problema a um conjunto enorme de configurações conferidas por computador. Em 1996, Neil Robertson, Daniel Sanders, Paul Seymour e Robin Thomas apresentaram uma prova mais simples, ainda com computador, com 633 configurações; e em 2005 Georges Gonthier e Benjamin Werner formalizaram uma prova completa no assistente de provas Coq (veja o verbete Four color theorem).
Quatro cores sem quatro regiões mutuamente vizinhas. A roda com 5 raios — um ciclo \(C_5\) mais um vértice central ligado aos cinco — é planar e não contém \(K_4\): uma cópia de \(K_4\) precisaria de três vértices do ciclo mutuamente adjacentes, e \(C_5\) não tem triângulos. Mesmo assim, \(\chi = 4\). O ciclo \(C_5\) é ímpar e precisa de 3 cores, e o vértice central, vizinho de todos os vértices do ciclo, não pode repetir nenhuma delas. É o exemplo, na forma de grafo, que o primeiro artigo usou para mostrar que “não ter \(K_5\)” não explica, sozinho, por que quatro cores bastam: precisar de \(k\) cores não exige conter \(K_k\). A figura abaixo mostra o mapa e a roda lado a lado, com uma coloração de 4 cores:
A prova das Quatro Cores está fora do alcance de um artigo, mas a versão com seis cores sai do Corolário 1 em poucas linhas. O ponto de partida é um lema.
Todo grafo planar tem um vértice de grau no máximo 5.
Prova: Seja \(H\) um componente conexo do grafo planar \(G\); \(H\) também é planar. Se \(H\) tem no máximo 2 vértices, seus vértices têm grau no máximo 1. Caso contrário, \(H\) é conexo, planar e tem \(n_H \geq 3\) vértices, e o Corolário 1 dá \(m_H \leq 3n_H - 6\). Se todo vértice de \(H\) tivesse grau pelo menos 6, o Teorema do Aperto de Mãos daria \(2m_H = \sum d(v) \geq 6n_H\), ou seja, \(m_H \geq 3n_H > 3n_H - 6\) — uma contradição. Portanto, \(H\), e com ele \(G\), tem um vértice de grau no máximo 5, que é o que queríamos demonstrar. \(\blacksquare\)
Todo grafo planar \(G\) tem \(\chi(G) \leq 6\).
Prova por indução no número \(n\) de vértices:
Base: se \(n \leq 6\), basta dar uma cor diferente a cada vértice.
Hipótese de indução: suponha que todo grafo planar com \(n - 1\) vértices (\(n \geq 7\)) pode ser colorido com 6 cores.
Passo indutivo: seja \(G\) planar com \(n\) vértices. Pelo lema, \(G\) tem um vértice \(v\) com \(d(v) \leq 5\). Removendo \(v\) e suas arestas, obtemos \(G - v\), que é planar (é subgrafo de \(G\), Observação 2) e tem \(n - 1\) vértices; pela hipótese de indução, \(G - v\) pode ser colorido com 6 cores. Os no máximo 5 vizinhos de \(v\) usam no máximo 5 dessas cores, e sobra pelo menos uma para \(v\).
Portanto, todo grafo planar com \(n\) vértices pode ser colorido com 6 cores, isto é, \(\chi(G) \leq 6\), que é o que queríamos demonstrar. \(\blacksquare\)
Com mais trabalho — trocando cores ao longo de caminhos de duas cores alternadas, as “cadeias de Kempe” —, o mesmo lema dá o Teorema das Cinco Cores de Heawood. Para chegar a quatro, ninguém encontrou um argumento desse tamanho.
Conferindo com código
O networkx testa planaridade com nx.check_planarity e colore com
nx.greedy_color, que percorre os vértices numa ordem e dá a cada um a menor cor
ainda não usada pelos vizinhos. A coloração gulosa não garante o mínimo, mas na
estratégia "smallest_last" ela repete a prova das Seis Cores: tira um vértice de
grau mínimo, depois outro, e colore na ordem inversa. Por isso, num grafo planar,
essa estratégia nunca usa mais de 6 cores.
import networkx as nx
roda = nx.wheel_graph(6) # vértice 0 no centro, ligado ao ciclo 1-2-3-4-5
print(nx.check_planarity(roda)[0]) # True
cores = nx.greedy_color(roda, strategy="largest_first")
print(cores) # {0: 0, 1: 1, 2: 2, 3: 1, 4: 2, 5: 3}
print(len(set(cores.values()))) # 4
icosaedro = nx.icosahedral_graph() # planar, todos os vértices com grau 5
print(nx.check_planarity(icosaedro)[0]) # True
cores = nx.greedy_color(icosaedro, strategy="smallest_last")
print(len(set(cores.values()))) # 4A roda usa exatamente as quatro cores de que precisa. O icosaedro mostra que o lema não pode ser melhorado — ali todo vértice tem grau 5 — e, mesmo assim, a coloração gulosa encontra 4 cores.
Aplicação: horários sem conflito
Cinco comissões de uma empresa precisam se reunir, e duas comissões com um membro em comum não podem se reunir no mesmo horário. No grafo de conflitos, cada comissão é um vértice e cada membro compartilhado vira uma aresta; os horários são as cores, e o número mínimo de horários é \(\chi(G)\). A mesma modelagem distribui frequências de rádio entre antenas vizinhas e registradores do processador entre variáveis de um programa.
import networkx as nx
conflitos = nx.Graph([
("Orçamento", "Pessoal"), ("Orçamento", "Obras"), ("Pessoal", "Obras"),
("Pessoal", "Tecnologia"), ("Obras", "Tecnologia"), ("Tecnologia", "Eventos"),
])
horarios = nx.greedy_color(conflitos, strategy="largest_first")
print(horarios)
# Saída: {'Pessoal': 0, 'Obras': 1, 'Tecnologia': 2, 'Orçamento': 2, 'Eventos': 0}
print(max(horarios.values()) + 1) # 3 horáriosTrês horários são o mínimo: Orçamento, Pessoal e Obras formam uma clique com três vértices, e uma clique com \(k\) vértices exige \(k\) cores.
Tabela-Resumo #
| Conceito | Expressão/Definição |
|---|---|
| Grafo planar | Desenhável no plano sem cruzar arestas |
| Invariância de faces | Toda representação plana de um grafo conexo tem o mesmo número de faces \(f\) |
| Fórmula de Euler | \(n - m + f = 2\) (grafo planar conexo) |
| Limite geral | \(m \leq 3n - 6\) (necessário; \(n \geq 3\)) |
| Sem triângulos | \(m \leq 2n - 4\) (necessário; \(n \geq 3\)) |
| \(K_5\) | \(m = 10 > 9 = 3(5)-6\) → não planar |
| \(K_{3,3}\) | \(m = 9 > 8 = 2(6)-4\) → não planar |
| Herança de planaridade | Subgrafo de grafo planar é planar → grafo com subgrafo não planar é não planar |
| Kuratowski | Planar \(\iff\) sem subdivisão de \(K_5\) ou \(K_{3,3}\) como subgrafo |
| Fórmula de Euler geral | \(n - m + f = 1 + c\) (grafo planar com \(c\) componentes) |
| Número cromático | \(\chi(G)\) = menor número de cores com vizinhos de cores diferentes |
| Grau mínimo em planares | Todo grafo planar tem vértice de grau \(\leq 5\) |
| Teorema das Seis Cores | Grafo planar \(\Rightarrow \chi(G) \leq 6\) (prova por indução) |
| Teorema das Quatro Cores | Grafo planar \(\Rightarrow \chi(G) \leq 4\) (Appel e Haken, 1976) |
Exercícios #
Exercício 1: Número de faces
Um grafo planar conexo tem 8 vértices e 12 arestas. Quantas faces tem?
Solução: Da Fórmula de Euler: \(f = 2 - n + m = 2 - 8 + 12 = 6\) faces.
Exercício 2: \(K_{2,4}\) é planar?
Enunciado: O grafo bipartido completo \(K_{2,4}\) é planar?
Solução: \(K_{2,4}\) tem \(n = 6\), \(m = 8\). É bipartido (sem triângulos). Pelo Corolário 2: \(m \leq 2(6) - 4 = 8\). Como \(8 \leq 8\), o corolário não descarta a planaridade. De fato, \(K_{2,4}\) é planar — é possível desenhá-lo sem cruzamentos.
Exercício 3: subgrafo não planar
Um grafo \(G\) tem 8 vértices e 14 arestas, e você descobre que 5 desses vértices, junto com 10 das arestas entre eles, formam uma cópia de \(K_5\). O que se pode concluir sobre a planaridade de \(G\)?
Solução: Pela Observação 2’, se \(G\) contém um grafo não planar (\(K_5\)) como subgrafo, então \(G\) é não planar — independente do que acontece nos outros 3 vértices e nas outras 4 arestas.
Próximos Passos #
Tudo neste artigo tratou de desenhabilidade: se um grafo pode ser colocado no plano sem cruzar arestas. Em nenhum momento perguntamos se as conexões têm sentido único — se ir de \(A\) a \(B\) é a mesma coisa que ir de \(B\) a \(A\). É exatamente essa a limitação que fecha esta etapa da série: planaridade nada diz sobre a direção das conexões. No próximo artigo desta série, estudamos grafos direcionados — quando a direção das conexões importa.
