Teorema das quatro cores

Em matemática, o teorema das quatro cores, ou teorema do mapa das quatro cores, afirma que não mais do que quatro cores são necessárias para colorir as regiões de qualquer mapa, de modo que duas regiões adjacentes não tenham 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.[1] Foi o primeiro teorema importante a ser provado usando um computador. Inicialmente, essa 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.[2] Desde então, a prova ganhou ampla aceitação, embora alguns questionadores permaneçam.[3]

Abstração de um mapa com 4 cores usando grafos
Mapa dos Estados Unidos desenhado com 4 cores; observe que até em estados que fazem fronteira com mais outros 3 estados não acabam coincidindo suas cores
Diagrama com quatro cores

A sua formulação é a seguinte:

Dado um mapa plano, dividido em regiões, quatro cores são suficientes para colori-lo de forma a que regiões vizinhas não partilhem a mesma cor.

O teorema das quatro cores foi provado em 1976 por Kenneth Appel e Wolfgang Haken após muitas provas e contra-exemplos falsos (ao contrário do teorema das cinco cores, provado na década de 1800, que afirma que cinco cores são suficientes para colorir um mapa). Para dissipar quaisquer dúvidas remanescentes sobre a prova Appel-Haken, uma prova mais simples usando as mesmas idéias e ainda contando com computadores foi publicada em 1997 por Robertson, Sanders, Seymour e Thomas. Além disso, em 2005, o teorema foi provado por Georges Gonthier com software de prova de teorema de uso geral.[4][5]

Referências

  1. From Gonthier (2008): "Definitions: A planar map is a set of pairwise disjoint subsets of the plane, called regions. A simple map is one whose regions are connected open sets. Two regions of a map are adjacent if their respective closures have a common point that is not a corner of the map. A point is a corner of a map if and only if it belongs to the closures of at least three regions. Theorem: The regions of any simple planar map can be colored with only four colors, in such a way that any two adjacent regions have different colors."
  2. Swart (1980).
  3. Wilson (2014), 216–222.
  4.    (25 de outubro de 2001). «Folha Online - Educação - Resumão/matemática - O teorema das quatro cores e o Mercosul - 25/10/2001 10h39». .folha.uol.com.br. Consultado em 20 de setembro de 2012 
  5. «The Four Color Theorem». Mathpages.com. Consultado em 20 de setembro de 2012 

FontesEditar

  Este artigo sobre matemática é um esboço. Você pode ajudar a Wikipédia expandindo-o.