Cornered Snowflake) que tinha certeza de que a maneira mais eficiente de embalarmos esferas
num espaço tridimensional é um arranjo utilizado por muitos verdureiros para empilhar
laranjas: uma série de camadas semelhantes a favos de mel empilhados uns sobre os outros, de
modo que cada camada se encaixe nas reentrâncias da camada inferior. Em 1998, Thomas
Hales anunciou ter encontrado uma prova dessa conjectura com o auxílio do computador, que
foi posteriormente publicada. A conjectura das quatro cores, que tem cerca de 100 anos,
questionava se seria possível colorirmos qualquer mapa num plano usando no máximo quatro
cores, de modo que as regiões adjacentes sempre tivessem cores diferentes. Foi provada por
Kenneth Appel e Wolfgang Haken em 1976, novamente com o auxílio do computador.
O teorema das quatro cores, como é chamado agora, pertence a uma área da matemática
conhecida como teoria dos grafos. Lembre-se de que um grafo é uma coleção de “vértices”
representados por pontos, unidos por “arestas” representadas por linhas. Um mapa no plano e
a noção de “região adjacente” podem ser codificados na forma de um grafo. Temos um vértice
para cada região, e as arestas unem vértices correspondentes a regiões adjacentes. Portanto, o
problema das Quatro Cores pode ser reformulado, transformando-se num problema sobre
como colorir os vértices de um certo grafo.
A teoria dos grafos nos apresenta muitos problemas simples de propor e difíceis de
resolver. Muitos deles ainda estão em aberto, e uma área que abrange muitas dessas questões
está ligada ao número de cruzamentos de um grafo. Desenhe o grafo no plano (ou numa folha
de papel, se preferir) de modo que o número de cruzamentos entre as arestas seja o menor
possível (as arestas só podem tocar os vértices em suas extremidades e devem se cruzar em
pontos isolados). Esse menor número de cruzamentos é, claro, o número de cruzamentos citado
antes. Nadine Myers, da Universidade Hamline, discutiu essa questão na Mathematics
Magazine, em 1998. Ela citou um comentário feito por Paul Erdös e Richard K. Guy em 1970:
“Quase todas as perguntas que podemos fazer sobre os números de cruzamentos continuam em
aberto.” O comentário ainda é perfeitamente válido. Na verdade, é incrível o pouco que
sabemos sobre o número de cruzamentos.
Embora pareça ser muito difícil provar fatos sobre os números de cruzamentos, os
matemáticos recreativos podem se divertir bastante fazendo experimentos com diagramas de
grafos e tentando reduzir o número de cruzamentos. Esse tipo de experimento tem a
possibilidade de até refutar certas conjecturas notáveis, reduzindo o número de cruzamentos a
um valor menor que o conjecturado.
Os grafos com números de cruzamentos iguais a zero já foram completamente
caracterizados, num resultado que data de 1930 e é conhecido como o teorema de Kuratowski,
por ter sido provado por Kazimierz Kuratowski. Tais grafos são planares — podem ser
desenhados no plano sem nenhum cruzamento. O grafo da Figura 13.1.a é de fato planar.
Embora esteja desenhado com quatro cruzamentos, podemos mover as arestas e vértices de
modo a nos livrarmos de todos os cruzamentos, como na Figura 13.1.b. Na verdade, esse grafo
é apenas um “ciclo” em seis vértices (seis vértices unidos, formando um anel). Podemos
definir grafos semelhantes com n vértices, denotando-os pelo símbolo Cn. Portanto, esse grafo
é C 6.
O teorema de Kuratowski afirma que um grafo é planar se não contiver (num sentido
ligeiramente técnico) nenhum dos grafos mostrados na Figura 13.2.a e 13.2.b. (Observe que, ao
longo das arestas desses grafos, podem ocorrer vértices que as subdividam.) A Figura 13.2.a
(ignorando esses vértices adicionais) é chamada de “grafo completo com cinco vértices”: cada
vértice está unido a todos os outros. Existem grafos completos análogos, com qualquer número
de vértices. Se tiver n vértices, esse grafo será denotado por Kn. Já o encontramos no Capítulo
- Para relembrar, a Figura 13.2.a ilustra K 5. A Figura 13.2.b (novamente ignorando os
vértices extras) é o “grafo bipartido completo de dois conjuntos de três vértices”. Os vértices