Teorema das quatro cores
Na matemática, o teorema das quatro cores, ou o teorema do mapa de quatro cores, afirma que não são necessárias mais de quatro cores para colorir as regiões de qualquer mapa de modo que não há duas regiões adjacentes com a mesma cor. Adjacente significa que duas regiões compartilham um segmento de curva limite comum, não apenas um canto onde três ou mais regiões se encontram. Foi o primeiro grande teorema a ser provado usando um computador. Inicialmente, esta prova não foi aceita por todos os matemáticos porque a prova assistida por computador era inviável para um ser humano verificar manualmente. A prova ganhou ampla aceitação desde então, embora algumas dúvidas permaneçam.
O teorema das quatro cores foi provado em 1976 por Kenneth Appel e Wolfgang Haken após muitas provas falsas e contra-exemplos (ao contrário do teorema das cinco cores, provado em 1800, que afirma que cinco cores são suficientes para colorir um mapa). Para dissipar quaisquer dúvidas remanescentes sobre a prova de Appel-Haken, uma prova mais simples usando as mesmas ideias e ainda contando com computadores foi publicada em 1997 por Robertson, Sanders, Seymour e Thomas. Em 2005, o teorema também foi provado por Georges Gonthier com software de prova de teorema de uso geral.
Formulação precisa do teorema
Em termos grafos-teóricos, o teorema afirma que para grafo planar sem loop GNão. G., seu número cromático é χ χ (G)≤ ≤ 4{displaystyle chi (G)leq 4}.
A declaração intuitiva do teorema das quatro cores - "dada qualquer separação de um plano em regiões contíguas, as regiões podem ser coloridas usando no máximo quatro cores, de modo que não haja duas regiões adjacentes com a mesma cor" – precisa ser interpretado apropriadamente para estar correto.
Primeiro, as regiões são adjacentes se compartilham um segmento de fronteira; duas regiões que compartilham apenas pontos de fronteira isolados não são consideradas adjacentes. (Caso contrário, um mapa em forma de gráfico de pizza criaria um número arbitrariamente grande de regiões 'adjacentes' umas às outras em um canto comum e, como resultado, exigiria um número arbitrariamente grande de cores.) Em segundo lugar, regiões bizarras, como aquelas com área finita, mas perímetro infinitamente longo, não são permitidas; mapas com essas regiões podem exigir mais de quatro cores. (Para garantir, podemos restringir a regiões cujos limites consistem em um número finito de segmentos de linha reta. É permitido que uma região tenha enclaves, ou seja, ela envolve inteiramente uma ou mais outras regiões.) Observe que a noção de " região contígua" (tecnicamente: subconjunto aberto conectado do plano) não é o mesmo que o de um "país" em mapas regulares, uma vez que os países não precisam ser contíguos (eles podem ter exclaves, por exemplo, a Província de Cabinda como parte de Angola, Nakhchivan como parte do Azerbaijão, Kaliningrado como parte da Rússia, a França com seus territórios ultramarinos e o Alasca como parte do Estados Unidos não são contíguos). Se exigimos que todo o território de um país receba a mesma cor, então quatro cores nem sempre são suficientes. Por exemplo, considere um mapa simplificado:
Neste mapa, as duas regiões identificadas como A pertencem ao mesmo país. Se quiséssemos que essas regiões recebessem a mesma cor, seriam necessárias cinco cores, pois as duas regiões A juntas são adjacentes a outras quatro regiões, cada uma adjacente a todas as outras. Forçar duas regiões separadas a terem a mesma cor pode ser modelado adicionando uma 'alça' juntando-se a eles fora do avião.
Essa construção torna o problema equivalente a colorir um mapa em um toro (uma superfície do gênero 1), que requer até 7 cores para um mapa arbitrário. Uma construção semelhante também se aplica se uma única cor for usada para várias áreas disjuntas, como para corpos d'água em mapas reais, ou se houver mais países com territórios disjuntos. Em tais casos, mais cores podem ser necessárias com um gênero crescente de uma superfície resultante. (Consulte a seção Generalizações abaixo.)
Uma declaração mais simples do teorema usa a teoria dos grafos. O conjunto de regiões de um mapa pode ser representado de forma mais abstrata como um grafo não direcionado que possui um vértice para cada região e uma aresta para cada par de regiões que compartilham um segmento de fronteira. Este grafo é planar: pode ser desenhado no plano sem cruzamentos, colocando cada vértice em um local escolhido arbitrariamente dentro da região a que corresponde, e desenhando as arestas como curvas sem cruzamentos que partem do vértice de uma região, através de um segmento de limite compartilhado, até o vértice de uma região adjacente. Por outro lado, qualquer gráfico planar pode ser formado a partir de um mapa dessa maneira. Na terminologia da teoria dos grafos, o teorema das quatro cores afirma que os vértices de todo grafo planar podem ser coloridos com no máximo quatro cores, de modo que dois vértices adjacentes não recebam a mesma cor, ou para abreviar:
- Cada gráfico planar é quatro cores.
História
Tentativas iniciais de prova
Até onde se sabe, a conjectura foi proposta pela primeira vez em 23 de outubro de 1852, quando Francis Guthrie, ao tentar colorir o mapa dos condados da Inglaterra, notou que eram necessárias apenas quatro cores diferentes. Na época, o irmão de Guthrie, Frederick, era aluno de Augustus De Morgan (ex-conselheiro de Francis) na University College London. Francis perguntou a Frederick sobre isso, que então o levou para De Morgan (Francis Guthrie se formou mais tarde em 1852 e mais tarde tornou-se professor de matemática na África do Sul). Segundo De Morgan:
"Um estudante meu [Guthrie] me pediu hoje para dar-lhe uma razão para um fato que eu não sabia era um fato - e ainda não. Ele diz que se uma figura for dividida e os compartimentos de forma diferente coloridos para que figuras com qualquer parte do limite comum linha de linha são diferentemente coloridos - quatro cores podem ser desejadas, mas não mais - o seguinte é o seu caso em que quatro cores são queria. A consulta não pode ser inventada uma necessidade para cinco ou mais..." (Wilson 2014, p. 18)
"F.G.", talvez um dos dois Guthries, publicou a questão no The Athenaeum em 1854, e De Morgan colocou a questão novamente na mesma revista em 1860. Outra referência publicada anteriormente por Arthur Cayley (1879), por sua vez, credita a conjectura a De Morgan.
Houve várias tentativas iniciais fracassadas de provar o teorema. De Morgan acreditava que isso decorria de um simples fato sobre quatro regiões, embora não acreditasse que esse fato pudesse ser derivado de fatos mais elementares.
Isso surge da seguinte maneira. Nós nunca precisamos de quatro cores em um bairro a menos que haja quatro condados, cada um dos quais tem linhas de fronteira em comum com cada um dos outros três. Tal coisa não pode acontecer com quatro áreas a menos que uma ou mais delas sejam fechadas pelo resto; e a cor usada para o condado fechado é, portanto, livre para continuar. Agora, este princípio, que quatro áreas não podem cada uma ter fronteira comum com todos os outros três sem inclosure, não é, nós acreditamos plenamente, capaz de demonstrar sobre qualquer coisa mais evidente e mais elementar; ele deve estar como um postulado.
Uma prova proposta foi dada por Alfred Kempe em 1879, que foi amplamente aclamada; outro foi dado por Peter Guthrie Tait em 1880. Não foi até 1890 que a prova de Kempe foi mostrada incorreta por Percy Heawood, e em 1891, a prova de Tait foi mostrada incorreta por Julius Petersen - cada prova falsa permaneceu incontestado por 11 anos.
Em 1890, além de expor a falha na prova de Kempe, Heawood provou o teorema das cinco cores e generalizou a conjectura das quatro cores para superfícies de gênero arbitrário.
Tait, em 1880, mostrou que o teorema das quatro cores é equivalente à afirmação de que um certo tipo de gráfico (chamado de snark na terminologia moderna) deve ser não planar.
Em 1943, Hugo Hadwiger formulou a conjectura de Hadwiger, uma generalização abrangente do problema das quatro cores que ainda permanece sem solução.
Prova por computador
Durante as décadas de 1960 e 1970, o matemático alemão Heinrich Heesch desenvolveu métodos de uso de computadores para procurar uma prova. Notavelmente, ele foi o primeiro a usar a descarga para provar o teorema, o que acabou sendo importante na parte de inevitabilidade da subsequente prova de Appel-Haken. Ele também expandiu o conceito de redutibilidade e, junto com Ken Durre, desenvolveu um teste de computador para isso. Infelizmente, nessa conjuntura crítica, ele não conseguiu obter o tempo necessário do supercomputador para continuar seu trabalho.
Outros adotaram seus métodos, incluindo sua abordagem assistida por computador. Enquanto outras equipes de matemáticos corriam para completar as provas, Kenneth Appel e Wolfgang Haken, da Universidade de Illinois, anunciaram, em 21 de junho de 1976, que haviam provado o teorema. Eles foram auxiliados em algum trabalho algorítmico por John A. Koch.
Se a conjectura das quatro cores fosse falsa, haveria pelo menos um mapa com o menor número possível de regiões que requer cinco cores. A prova mostrou que tal contra-exemplo mínimo não pode existir, através do uso de dois conceitos técnicos:
- Um conjunto inevitável é um conjunto de configurações, de tal forma que cada mapa que satisfaça algumas condições necessárias para ser uma triangulação não-4-colorível mínima (como ter grau mínimo 5) deve ter pelo menos uma configuração deste conjunto.
- A configuração redutível é um arranjo de países que não podem ocorrer em um contra-exemplo mínimo. Se um mapa contém uma configuração redutível, o mapa pode ser reduzido a um mapa menor. Este mapa menor tem a condição de que se ele pode ser colorido com quatro cores, isso também se aplica ao mapa original. Isso implica que se o mapa original não puder ser colorido com quatro cores o mapa menor não pode nem e assim o mapa original não é mínimo.
Usando regras e procedimentos matemáticos baseados em propriedades de configurações redutíveis, Appel e Haken encontraram um conjunto inevitável de configurações redutíveis, provando assim que não poderia existir um contra-exemplo mínimo para a conjectura das quatro cores. A prova deles reduziu a infinidade de mapas possíveis a 1.834 configurações redutíveis (posteriormente reduzidas a 1.482) que tiveram de ser verificadas uma a uma por computador e levaram mais de mil horas. Esta parte da redutibilidade do trabalho foi verificada de forma independente com diferentes programas e computadores. No entanto, a parte inevitável da prova foi verificada em mais de 400 páginas de microfichas, que tiveram que ser verificadas manualmente com a ajuda da filha de Haken, Dorothea Blostein (Appel & Haken 1989).
O anúncio de Appel e Haken foi amplamente divulgado pela mídia de notícias em todo o mundo, e o departamento de matemática da Universidade de Illinois usou um carimbo postal afirmando "Quatro cores bastam." Ao mesmo tempo, a natureza incomum da prova - foi o primeiro grande teorema a ser provado com extensa assistência de computador - e a complexidade da parte verificável por humanos gerou considerável controvérsia (Wilson 2014).
No início dos anos 80, espalharam-se rumores sobre uma falha na prova de Appel-Haken. Ulrich Schmidt, da RWTH Aachen, examinou a prova de Appel e Haken para sua tese de mestrado publicada em 1981 (Wilson 2014, 225). Ele verificou cerca de 40% da parte inevitável e encontrou um erro significativo no procedimento de descarga (Appel & Haken 1989). Em 1986, Appel e Haken foram solicitados pelo editor do Mathematical Intelligencer a escrever um artigo abordando os rumores de falhas em sua prova. Eles responderam que os rumores se deviam a uma "má interpretação dos resultados de [Schmidt]" e obrigado com um artigo detalhado (Wilson 2014, 225–226). Sua magnum opus, Cada Mapa Planar é Quatro-Colorível, um livro que reivindica uma prova completa e detalhada (com um suplemento de microficha de mais de 400 páginas), apareceu em 1989; ele explicou e corrigiu o erro descoberto por Schmidt, bem como vários outros erros encontrados por outros (Appel & Haken 1989).
Simplificação e verificação
Desde a prova do teorema, uma nova abordagem levou a uma prova mais curta e a um algoritmo mais eficiente para mapas de 4 cores. Em 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour e Robin Thomas criaram um algoritmo de tempo quadrático (exigindo apenas O(n2), onde n é o número de vértices), melhorando um algoritmo de tempo quártico baseado na prova de Appel e Haken. A nova prova, baseada nas mesmas ideias, é semelhante à de Appel e Haken, mas mais eficiente porque reduz a complexidade do problema e requer a verificação de apenas 633 configurações redutíveis. As partes de inevitabilidade e redutibilidade desta nova prova devem ser executadas por um computador e são impraticáveis para verificação manual. Em 2001, os mesmos autores anunciaram uma prova alternativa, provando a conjectura de snark. Esta prova permanece inédita, no entanto.
Em 2005, Benjamin Werner e Georges Gonthier formalizaram uma prova do teorema dentro do assistente de prova Coq. Isso eliminou a necessidade de confiar nos vários programas de computador usados para verificar casos específicos; é necessário apenas confiar no kernel Coq.
Resumo de ideias de prova
A discussão a seguir é um resumo baseado na introdução de Todo mapa planar é quatro cores (Appel & Haken 1989). Embora falho, a suposta prova original de Kempe do teorema das quatro cores forneceu algumas das ferramentas básicas usadas posteriormente para prová-lo. A explicação aqui é reformulada em termos da formulação da teoria dos grafos moderna acima.
O argumento de Kempe é o seguinte. Primeiro, se regiões planas separadas pelo grafo não são trianguladas, ou seja, não possuem exatamente três arestas em seus limites, podemos adicionar arestas sem introduzir novos vértices para tornar cada região triangular, incluindo a ilimitada região externa. Se esse grafo triangulado for colorível usando quatro cores ou menos, o grafo original também será, pois a mesma coloração é válida se as arestas forem removidas. Portanto, basta provar o teorema das quatro cores para grafos triangulados para prová-lo para todos os grafos planares e, sem perda de generalidade, assumimos que o grafo é triangulado.
Suponha que v, e e f sejam o número de vértices, arestas e regiões (faces). Como cada região é triangular e cada aresta é compartilhada por duas regiões, temos que 2e = 3f. Isso junto com a fórmula de Euler, v − e + f = 2, pode ser usado para mostrar que 6v − 2e = 12. Agora, o grau de um vértice é o número de arestas adjacentes a ele. Se vn é o número de vértices de grau n e D é o grau máximo de qualquer vértice,
- 6v- Sim. - Sim. 2e= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =6Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1DvEu...- Sim. - Sim. Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1DEu...vEu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1D(6- Sim. - Sim. Eu...)vEu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =12.{displaystyle 6v-2e=6sum _{i=1}^{D}v_{i}-sum _{i=1}^{D}iv_{i}=sum _{i=1}^{D}(6-i)v_{i}=12.}
Mas desde 12 > 0 e 6 − i ≤ 0 para todo i ≥ 6, isso demonstra que existe pelo menos um vértice de grau 5 ou menor.
Se houver um grafo que requer 5 cores, então existe um grafo mínimo, onde a remoção de qualquer vértice torna-o quadricolor. Chame esse gráfico de G. Então G não pode ter um vértice de grau 3 ou menor, porque se d(v) ≤ 3, podemos remover v de G, pinte o gráfico menor com quatro cores, então adicione v de volta e estenda a quadricoloração para ele escolhendo uma cor diferente de seus vizinhos.
Kempe também mostrou corretamente que G não pode ter nenhum vértice de grau 4. Como antes, removemos o vértice v e colorimos os vértices restantes com quatro cores. Se todos os quatro vizinhos de v forem de cores diferentes, digamos vermelho, verde, azul e amarelo no sentido horário, procuramos um caminho alternado de vértices coloridos de vermelho e azul unindo os vizinhos vermelho e azul. Esse caminho é chamado de cadeia de Kempe. Pode haver uma cadeia Kempe unindo os vizinhos vermelho e azul, e pode haver uma cadeia Kempe unindo os vizinhos verde e amarelo, mas não ambos, pois esses dois caminhos necessariamente se cruzariam, e o vértice onde eles se cruzam não pode ser colorido. Suponha que sejam os vizinhos vermelho e azul que não estão encadeados. Explore todos os vértices ligados ao vizinho vermelho por caminhos alternados vermelho-azul e, em seguida, inverta as cores vermelho e azul em todos esses vértices. O resultado ainda é uma quatro cores válida, e v agora pode ser adicionado de volta e colorido de vermelho.
Isso deixa apenas o caso em que G tem um vértice de grau 5; mas o argumento de Kempe foi falho para este caso. Heawood percebeu o erro de Kempe e também observou que, se alguém estivesse satisfeito em provar que apenas cinco cores são necessárias, poderia executar o argumento acima (mudando apenas que o contra-exemplo mínimo requer 6 cores) e usar cadeias de Kempe no grau 5 situação para provar o teorema das cinco cores.
Em qualquer caso, para lidar com este caso de vértice de grau 5 requer uma noção mais complicada do que remover um vértice. Em vez disso, a forma do argumento é generalizada para considerar configurações, que são subgrafos conectados de G com o grau de cada vértice (em G) especificado. Por exemplo, o caso descrito na situação de vértice de grau 4 é a configuração que consiste em um único vértice rotulado como tendo grau 4 em G. Como acima, basta demonstrar que se a configuração for removida e o gráfico restante for quadricolor, então a coloração pode ser modificada de tal forma que quando a configuração for adicionada novamente, a quadricoloração pode ser estendida a ela como bem. Uma configuração para a qual isso é possível é chamada de configuração redutível. Se pelo menos uma de um conjunto de configurações deve ocorrer em algum lugar em G, esse conjunto é chamado de inevitável. O argumento acima começou dando um conjunto inevitável de cinco configurações (um único vértice com grau 1, um único vértice com grau 2,..., um único vértice com grau 5) e então passou a mostrar que os primeiros 4 são redutíveis; exibir um conjunto inevitável de configurações onde cada configuração no conjunto é redutível provaria o teorema.
Como G é triangular, o grau de cada vértice em uma configuração é conhecido e todas as arestas internas à configuração são conhecidas, o número de vértices em G adjacentes a uma determinada configuração é fixo, e eles são unidos em um ciclo. Esses vértices formam o anel da configuração; uma configuração com k vértices em seu anel é uma configuração de k-anel, e a configuração junto com seu anel é chamada de configuração em anel. Como nos casos simples acima, pode-se enumerar todas as quatro cores distintas do anel; qualquer coloração que pode ser estendida sem modificação para uma coloração da configuração é chamada de inicialmente boa. Por exemplo, a configuração de vértice único acima com 3 ou menos vizinhos foi inicialmente boa. Em geral, o grafo circundante deve ser sistematicamente recolorido para tornar a coloração do anel boa, como foi feito no caso acima onde havia 4 vizinhos; para uma configuração geral com um anel maior, isso requer técnicas mais complexas. Devido ao grande número de quatro cores distintas do anel, esta é a etapa principal que requer assistência do computador.
Finalmente, resta identificar um conjunto incontornável de configurações passíveis de redução por este procedimento. O método primário usado para descobrir tal conjunto é o método de descarga. A ideia intuitiva subjacente à descarga é considerar o grafo planar como uma rede elétrica. Inicialmente positiva e negativa "carga elétrica" é distribuído entre os vértices de modo que o total seja positivo.
Lembre-se da fórmula acima:
- Gerenciamento Gerenciamento Eu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =1D(6- Sim. - Sim. Eu...)vEu...= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =12.{displaystyle sum _{i=1}^{D}(6-i)v_{i}=12.}
Cada vértice recebe uma carga inicial de 6 graus(v). Então um "flui" a carga redistribuindo sistematicamente a carga de um vértice para seus vértices vizinhos de acordo com um conjunto de regras, o procedimento de descarga. Como a carga é preservada, alguns vértices ainda têm carga positiva. As regras restringem as possibilidades de configurações de vértices carregados positivamente, portanto, enumerar todas essas configurações possíveis fornece um conjunto inevitável.
Desde que algum membro do conjunto inevitável não seja redutível, o procedimento de descarga é modificado para eliminá-lo (enquanto introduz outras configurações). O procedimento de descarga final de Appel e Haken foi extremamente complexo e, juntamente com uma descrição do conjunto de configurações inevitável resultante, preencheu um volume de 400 páginas, mas as configurações geradas poderiam ser verificadas mecanicamente para serem redutíveis. A verificação do volume que descreve o conjunto de configurações inevitável em si foi feita por revisão por pares durante um período de vários anos.
Um detalhe técnico não discutido aqui, mas necessário para concluir a prova, é a redutibilidade por imersão.
Falsas refutações
O teorema das quatro cores tem sido notório por atrair um grande número de falsas provas e refutações em sua longa história. A princípio, o The New York Times recusou-se, por uma questão de política, a relatar a prova de Appel-Haken, temendo que a prova se mostrasse falsa como as anteriores (Wilson 2014). Algumas supostas provas, como as de Kempe e Tait mencionadas acima, ficaram sob escrutínio público por mais de uma década antes de serem refutadas. Mas muitos outros, de autoria de amadores, nunca foram publicados.
Geralmente, os contra-exemplos mais simples, embora inválidos, tentam criar uma região que toca todas as outras regiões. Isso força as regiões restantes a serem coloridas com apenas três cores. Como o teorema das quatro cores é verdadeiro, isso sempre é possível; no entanto, como a pessoa que desenha o mapa está focada em uma grande região, ela não consegue perceber que as regiões restantes podem, de fato, ser coloridas com três cores.
Esse truque pode ser generalizado: existem muitos mapas onde se as cores de algumas regiões forem selecionadas de antemão, torna-se impossível colorir as regiões restantes sem ultrapassar quatro cores. Um verificador casual do contra-exemplo pode não pensar em mudar as cores dessas regiões, de modo que o contra-exemplo pareça válido.
Talvez um efeito subjacente a esse equívoco comum seja o fato de que a restrição de cores não é transitiva: uma região só precisa ser colorida de maneira diferente das regiões que ela toca diretamente, não das regiões que tocam as regiões que ela toca. Se essa fosse a restrição, os grafos planares exigiriam um número arbitrariamente grande de cores.
Outras refutações falsas violam as suposições do teorema, como usar uma região que consiste em várias partes desconectadas ou impedir que regiões da mesma cor se toquem em um ponto.
Três cores
Embora todo mapa planar possa ser colorido com quatro cores, é NP-completo em complexidade decidir se um mapa planar arbitrário pode ser colorido com apenas três cores.
Um mapa cúbico pode ser colorido com apenas três cores se e somente se cada região interior tiver um número par de regiões vizinhas. No exemplo do mapa dos estados dos EUA, o Missouri sem litoral (MO) tem oito vizinhos (um número par): deve ter uma cor diferente de todos eles, mas os vizinhos podem alternar as cores, portanto, esta parte do mapa precisa de apenas três cores. No entanto, Nevada sem litoral (NV) tem cinco vizinhos (um número ímpar): um dos vizinhos deve ter uma cor diferente dele e de todos os outros, portanto, quatro cores são necessárias aqui.
Generalizações
Gráficos infinitos
O teorema das quatro cores se aplica não apenas a grafos planares finitos, mas também a grafos infinitos que podem ser desenhados sem cruzamentos no plano, e ainda mais geralmente a grafos infinitos (possivelmente com um número incontável de vértices) para os quais cada finito subgrafo é planar. Para provar isso, pode-se combinar uma prova do teorema para grafos planares finitos com o teorema De Bruijn–Erdős afirmando que, se todo subgrafo finito de um grafo infinito é k-colorível, então todo o grafo também é Nash-Williams k-colorível (1967). Isso também pode ser visto como uma consequência imediata do teorema de compacidade de Kurt Gödel para a lógica de primeira ordem, simplesmente expressando a colorabilidade de um grafo infinito com um conjunto de fórmulas lógicas.
Superfícies mais altas
Pode-se também considerar o problema de coloração em superfícies diferentes do plano. O problema na esfera ou no cilindro é equivalente ao do plano. Para superfícies fechadas (orientáveis ou não orientáveis) com gênero positivo, o número máximo p de cores necessárias depende da característica de Euler da superfície χ de acordo com a fórmula
- p= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =?7+49- Sim. - Sim. 24.χ χ 2Gerenciamento de contas,Não. p=leftlfloor {frac {7+{sqrt {49-24chi }}}{2}}rightrfloor}
onde os colchetes mais externos denotam a função do piso.
Alternativamente, para uma superfície orientável, a fórmula pode ser dada em termos do gênero de uma superfície, g:
- p= = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = = =?7+1+48g2Gerenciamento de contas.Não. p=leftlfloor {frac {7+{sqrt {1+48g}}}{2}}rightrfloor}
Esta fórmula, a conjectura de Heawood, foi proposta por P. J. Heawood em 1890 e, após contribuições de várias pessoas, provada por Gerhard Ringel e J. W. T. Youngs em 1968. A única exceção à fórmula é a garrafa de Klein, que tem característica de Euler 0 (portanto, a fórmula dá p = 7), mas requer apenas 6 cores, conforme demonstrado por Philip Franklin em 1934.
Por exemplo, o toro tem característica de Euler χ = 0 (e gênero g = 1) e, portanto, p = 7, portanto não são necessárias mais de 7 cores para colorir qualquer mapa em um toro. Este limite superior de 7 é nítido: certos poliedros toroidais, como o poliedro Szilassi, requerem sete cores.
Uma faixa de Möbius requer seis cores (Tietze 1910), assim como grafos 1-planares (grafos desenhados com no máximo um cruzamento simples por aresta) (Borodin 1984). Se ambos os vértices e as faces de um grafo planar são coloridos, de tal forma que não há dois vértices adjacentes, faces ou par vértice-face com a mesma cor, então novamente no máximo seis cores são necessárias (Borodin 1984).
Um toru radialmente simétrico de 7 cores - regiões do mesmo envoltório de cor ao longo de linhas pontilhadas
Um toro duplo de 8 cores (superfície de gênio-dois) – bolhas denota combinação única de duas regiões
Uma garrafa Klein de 6 cores
A subdivisão de uma tira de Möbius em seis regiões mutuamente adjacentes, exigindo seis cores. Os vértices e bordas da subdivisão formam uma incorporação do grafo de Tietze na faixa.
Modelo interativo de poliedro de Szilassi com cada um de 7 faces adjacentes a cada outro – na imagem SVG, mova o mouse para girá-lo
Prova sem palavras que o número de cores necessárias é inabalável em três ou mais dimensões
Para grafos cujos vértices são representados como pares de pontos em duas superfícies distintas, com arestas desenhadas como curvas não cruzadas em uma das duas superfícies, o número cromático pode ser no mínimo 9 e no máximo 12, mas mais preciso limites não são conhecidos; este é o problema Terra-Lua de Gerhard Ringel.
Regiões sólidas
Não há extensão óbvia do resultado da coloração para regiões sólidas tridimensionais. Usando um conjunto de n hastes flexíveis, pode-se fazer com que cada haste toque todas as outras hastes. O conjunto exigiria então n cores, ou n+1 incluindo o espaço vazio que também toca cada haste. O número n pode ser considerado qualquer número inteiro, tão grande quanto desejado. Tais exemplos eram conhecidos por Fredrick Guthrie em 1880 (Wilson 2014). Mesmo para cubóides paralelos ao eixo (considerados adjacentes quando dois cubóides compartilham uma área de fronteira bidimensional), um número ilimitado de cores pode ser necessário (Reed & Allwright 2008; Magnant & Martin (2011)).
Relação com outras áreas da matemática
Dror Bar-Natan deu uma declaração sobre álgebras de Lie e invariantes de Vassiliev que é equivalente ao teorema das quatro cores.
Use fora da matemática
Apesar da motivação de colorir mapas políticos de países, o teorema não é de particular interesse para os cartógrafos. De acordo com um artigo do historiador da matemática Kenneth May, "Mapas que utilizam apenas quatro cores são raros, e aqueles que geralmente requerem apenas três. Livros sobre cartografia e história da cartografia não mencionam a propriedade de quatro cores" (Wilson 2014, 2). Deve-se notar, porém, que a maioria dos mapas requer quatro cores, pois sempre que uma região é cercada por um número ímpar de regiões, são necessárias quatro cores. O teorema também não garante a exigência cartográfica usual de que regiões não contíguas de um mesmo país (como o enclave do Alasca e o resto dos Estados Unidos) sejam coloridas de forma idêntica.
Contenido relacionado
Análise complexa
Coeficiente binomial
Curva elíptica