Mania de Matematica 2 - Novos Enigmas e Desafios Matemáticos

arestas do grafo. Agora, imagine que a esfera é feita de um material elástico. Você poderá
puxar esse buraquinho, tornando-o cada vez maior. O resto da esfera se estica e deforma,
carregando o grafo com ela. Se puxarmos o suficiente, poderemos aplaná-la, formando um
disco. Apoiando o disco num plano, teremos agora um grafo do mapa num plano, sem nenhum
cruzamento de arestas.

Figura 9.1

Um mapa e seu grafo correspondente.

Se o mapa for desenhado em diversas esferas, faremos exatamente o mesmo em cada uma
delas, apoiando os discos resultantes no mesmo plano, sem sobreposições. O grafo resultante
será desconectado — formado por vários pedaços, um para cada esfera —, mas essa é uma
característica bastante comum dos grafos, permitida por sua definição, portanto não há
problema.

Um grafo importante para este capítulo é o grafo completo Kn, que possui n vértices e uma

aresta unindo cada par de vértices distintos. A Figura 9.2 ilustra K 5. Se n for maior ou igual a

5, o grafo Kn não será planar.

Figura 9.2

Um grafo completo Kn não planar.

Dizemos que um mapa (num plano, esfera, várias esferas, onde seja) é colorível por k se
suas regiões puderem ser coloridas, usando-se não mais que k cores, de modo que as regiões
que possuam curvas fronteiriças comuns recebam cores diferentes. (Regiões que se encontrem
somente num ponto, ou em infinitos pontos, podem, se necessário, receber a mesma cor.) A
propriedade análoga para um grafo utiliza ideias muito parecidas. Um grafo é colorível por k
se seus vértices puderem ser coloridos, usando-se não mais que k cores, de modo que vértices
unidos por uma aresta recebam cores diferentes. É fácil perceber que um mapa é colorível por
k se e somente se seu grafo for colorível por k. Basta colorirmos cada capital — cada vértice
no grafo — com a mesma cor de seu país.

O menor k possível é chamado de número cromático do grafo: ele nos informa o número