mínimo de cores diferentes necessárias para colorir esse grafo — e, portanto, para colorir o
mapa correspondente, caso se trate do grafo de um mapa. É evidente que o número cromático
de Kn é n, pois cada vértice está unido a todos os demais, portanto não poderá haver dois
vértices da mesma cor.
A matemática vem estudando problemas de coloração há cerca de um século. O resultado
mais conhecido é o famoso teorema das quatro cores, que afirma que todos os mapas no plano
podem ser coloridos com quatro cores. Percy Heawood provou, há muito tempo, que todos os
mapas planares podem ser coloridos com cinco cores: como já comentado, em 1976 esse
número foi reduzido a quatro por Kenneth Appel e Wolfgang Haken, num impressionante
trabalho que combinou análise matemática e extensas buscas e cálculos computadorizados. Até
hoje não se conhece qualquer prova que dispense o amplo uso de computadores, embora a
prova de Appel-Haken tenha sido consideravelmente simplificada. Além disso, têm sido
estudadas muitas generalizações — entre elas, a dos mapas Terra/Lua que mencionei no
começo deste capítulo.
Um problema bastante relacionado ao dos mapas Terra/Lua foi apresentado por Percy
Heawood em 1890. O problema se passa apenas na Terra, mas, nele, cada país faz parte de um
império que contém um máximo de m países, e todos os países de certo império devem ser
coloridos com a mesma cor, de modo que as regiões adjacentes sempre tenham cores
diferentes. (Presume-se que os países de um mesmo império não fazem fronteira uns com os
outros.) Esse tipo de mapa é chamado de m-pério. Heawood provou que qualquer m-pério
pode ser colorido com 6m cores, para qualquer m ≥ 2.
Como o m-pério é um tipo particular de mapa, possui um grafo associado, com um vértice
por país. No entanto, não podemos mais dizer que cada coloração válida do grafo corresponde
a uma coloração do império. Isso ocorre porque as regras habituais de coloração do grafo não
preenchem a condição de que os vértices do mesmo império devem receber a mesma cor. É
difícil lidarmos com essa situação usando o grafo do mapa. Em vez disso, podemos modificar
a construção do grafo para que as regras de coloração se corrijam automaticamente.
Veja como.
O grafo do m-pério associado a um certo mapa do m-pério tem um vértice para cada
império (e não para cada região). Se isso parece confuso, pense no vértice como uma
representação do imperador. Dois vértices são unidos por uma aresta se e somente se os
impérios correspondentes contiverem ao menos um par de países adjacentes. Poderíamos
pensar no grafo do m-pério como o “grafo de invasão” dos imperadores cujos impérios podem
entrar em guerra numa fronteira comum. Um vértice por imperador, uma aresta para cada
guerra possível entre dois impérios.
Conceitualmente, obtemos o grafo do m-pério a partir do grafo comum identificando todos
os vértices de um certo império — desenhando-os exatamente no mesmo lugar. Essa
construção muitas vezes gera arestas múltiplas — dois vértices unidos por diversas arestas,
em vez de uma só. Removemos então essas arestas supérfluas, deixando apenas uma.
Ao identificarmos todos os vértices de um certo império, automaticamente os forçamos a
receber a mesma cor, portanto o número de cores necessárias para um m-pério é igual ao
número cromático de seu grafo.
Em 1983, Brad Jackson (Universidade Estadual de San José) e Gerhard Ringel
(Universidade da Califórnia, Santa Cruz) usaram essa abordagem para provar que o número
6 m do teorema de Heawood não pode ser reduzido. Eles chegaram a esse resultado ao
demonstrarem que podemos encontrar um m-pério que seja representado pelo grafo completo
K6m. Como K6m certamente precisa de 6m cores, existe um m-pério que não pode ser colorido
com menos de 6m cores.