miniatura|Exemple d'un mapa de quatre colors. miniatura|Mapa del món acolorit de color verd, taronja, blau i porpra. miniatura|Un mapa de quatre colors dels estats dels Estats Units (sense tenir en compte els llacs). miniatura|Mapa administratiu de Rússia acolorit amb quatre colors En matemàtiques, el teorema dels quatre colors estableix que en qualsevol partició d'un pla en regions contigües, que produeix una figura anomenada mapa, no es necessiten més de quatre colors per a acolorir les regions del mapa de manera que no hi hagi dues regions adjacents del mateix color. Dues regions s'anomenen adjacents si comparteixen una frontera comuna que no sigui una cantonada, on les cantonades són els punts compartits per tres o més regions. Per exemple, al mapa dels Estats Units d'Amèrica, Utah i Arizona són adjacents, però Utah i Nou Mèxic, que només comparteixen un punt que també pertany a Arizona i Colorado, no ho són.
Tot i la motivació d'acolorir els mapes polítics dels països, la cartografia no està particularment interessada en el teorema. Segons un article de l'historiador de matemàtiques Kenneth May, "són rars els mapes que utilitzen només quatre colors, i dels que ho fan en general només en necessiten tres. Els llibres de cartografia i història de la cartografia no esmenten la propietat dels quatre colors".
En els mapes més simples tres colors són suficients, però en alguns casos es necessita un quart color addicional per a alguns mapes, com ara aquells en els quals una regió està envoltada per un nombre senar d'altres regions que es toquen en un cicle. El teorema dels cinc colors, que té una curta demostració elemental, estableix que cinc colors són suficients per acolorir un mapa i es va demostrar el segle XIX; en canvi, demostrar que quatre colors són suficients va resultar ser significativament més difícil. Hi ha hagut una sèrie de demostracions i contraexemples falses des del primer enunciat del teorema dels quatre colors el 1852.
El teorema dels quatre colors va ser demostrat el 1976 per Kenneth Appel i Wolfgang Haken. Va ser el primer teorema important en ser demostrat mitjançant un ordinador. L'enfocament d'Appel i Haken va començar mostrant que hi ha un conjunt particular de 1.936 mapes, cadascun dels quals no pot formar part d'un contraexemple de mida més petita pel teorema dels quatre colors. Appel i Haken van utilitzar un programa informàtic especialment dissenyat per confirmar que cadascun d'aquests mapes tenien la propietat de poder ser acolorits amb quatre colors. A més, qualsevol mapa (independentment de si es tracta d'un contraexemple o no) ha de tenir una porció que s'assembla a un d'aquests 1.936 mapes. Demostrar això va requerir centenars de pàgines d'anàlisi a mà. Appel i Haken van arribar a la conclusió que no existien contraexemples més petits, ja que qualsevol hauria de contenir, però en canvi no conté, un d'aquests 1.936 mapes. Aquesta contradicció significa que no hi ha en realitat cap contraexemple i que, per tant, el teorema és cert. Inicialment, la seva demostració no va ser acceptada per tots els matemàtics, perquè la demostració assistida per ordinador era impossible de comprovar a mà per un humà. Des de llavors, la prova ha guanyat més acceptació, encara que persisteixen alguns dubtes.
Per dissipar els dubtes restants sobre la demostració d'Appel-Haken, el 1997 Robertson, Sanders, Seymour i Thomas van publicar una demostració més senzilla que utilitzava les mateixes idees i que seguia basant-se en els ordinadors. A més, el 2005 Georges Gonthier va demostrar el teorema utilitzant programari de demostració de teoremes de propòsit general.
Formulació precisa del teorema El teorema dels quatres colors es pot enunciar de manera intuïtiva com
miniatura|esquerra|Exemple d'un mapa de l'Azerbaidjan amb regions no contigües Perquè aquest enunciat intuïtiu del teorema dels quatre colors sigui correcte, cal interpretar-lo adequadament. En primer lloc, totes les cantonades, punts que pertanyen a tres o més països, s'han d'ignorar. A més, alguns mapes estranys (que per exemple utilitzin regions d'àrea finita però perímetre infinit) poden requerir més de quatre colors.
En segon lloc, per al propòsit del teorema cada "país" ha de ser una regió simplement connexa, o contigua. En el món real, això sovint no és així (per exemple, Michigan i la seva península superior, Nakhtxivan com a part de l'Azerbaidjan, i Kaliningrad com a part de Rússia no són contigus). Com que el territori d'un país en particular ha de ser del mateix color, en aquests casos quatre colors poden no ser suficients. Per exemple, consideri's un mapa simplificat:
center
En aquest mapa, les dues regions marcades A pertanyen a un mateix país, i han de ser del mateix color. Aquest mapa requereix per tant cinc colors, ja que les dues regions A juntes són contigües a quatre altres regions, cadascuna de les quals és contigua amb la resta. Si A es compongués de tres regions, es podrien necessitar sis o més colors; d'aquesta manera es poden construir mapes que requereixin un nombre arbitràriament alt de colors. Una construcció similar s'aplica també si s'utilitza un sol color per a tots els cossos d'aigua, com sol ser habitual en els mapes reals.
Transformació de mapa en graf Una versió més fàcil d'enunciar el teorema utilitza la teoria de grafs. El conjunt de les regions d'un mapa es pot representar de manera més abstracta com un graf no dirigit que té un vèrtex per a cada regió i una aresta per a cada parell de regions que comparteixen un segment de frontera. Aquest graf és pla (és important tenir en compte que estem parlant de grafs que tenen algunes limitacions només segons el mapa del qual provenen): es pot dibuixar en el pla sense encreuaments col·locant cada vèrtex en un emplaçament escollit arbitràriament dins de la regió a la qual correspon, i dibuixant les arestes com corbes que condueixen sense creuar cap regió des del vèrtex intern a una regió fins a un punt de la frontera compartida amb una altra regió. El mateix és cert en sentit contrari: a partir de qualsevol graf pla es pot dibuixar un mapa. En la terminologia de teoria de grafs, el teorema dels quatre colors enuncia que els vèrtexs de qualsevol graf pla es poden acolorir amb quatre colors com a màxim, de manera que cap parella de vèrtexs adjacents tinguin el mateix color, o de manera més concisa:
O equivalentment:
on és el nombre cromàtic del graf .
Història Intents de demostració inicials miniatura|esquerra|Augustus De Morgan Ja el 1840, Möbius va esmentar el problema en les seves conferències. La conjectura va ser proposada per primera vegada el 23 d'octubre de 1852, quan Francis Guthrie, en tractar d'acolorir el mapa dels comtats d'Anglaterra, es va adonar que només calien quatre colors diferents. En aquest moment, el germà de Guthrie, Frederick, era un estudiant d'Augustus De Morgan (l'exsupervisor de Francis) al University College de Londres. Francis ho va discutir amb Frederick, qui després va portar el problema a De Morgan (Francis Guthrie es va graduar més endavant, el 1852, i després es va convertir en professor de matemàtiques a Sud-àfrica). Segons De Morgan:
miniatura|Extracte de la carta original de De Morgan a Hamilton sobre la conjectura dels quatre colors (23 d'octubre de 1852, Trinity College, Dublin) "F.G.", potser un dels dos Guthries, va publicar la pregunta a l'Athenaeum, una revista londinenca, el 1854, i De Morgan va plantejar la pregunta de nou a la mateixa revista el 1860. Una altra referència publicada per Arthur Cayley al seu torn acredita la conjectura a De Morgan.
Hi va haver diversos intents fallits de demostrar el teorema. De Morgan creia que es desprenia d'un fet simple sobre quatre regions, tot i que no creia que aquest fet es pogués derivar de fets més elementals.
El 1879, Alfred Kempe va oferir una suposada demostració, que va ser àmpliament reconeguda; el 1880, Peter Guthrie Tait en va oferir una altra. No va ser fins al 1890 que Percy John Heawood va mostrar que la demostració de Kempe era incorrecta, i el 1891 Julius Petersen va mostrar que la demostració de Tait també era incorrecta —cada demostració errònia va romandre doncs indiscutida durant 11 anys.
El 1890, a més de mostrar els errors en la demostració de Kempe, Heawood va demostrar el teorema dels cinc colors i va generalitzar la conjectura dels quatre colors a superfícies arbitràries.
El 1880, Tait va mostrar que el teorema dels quatre colors és equivalent a l'afirmació que un cert tipus de graf (un graf connex, sense ponts, cúbic i de nombre cromàtic 4) ha de ser no-pla.
El 1943, Hugo Hadwiger va formular la conjectura de Hadwiger, una generalització de llarg abast del problema dels quatre colors que encara segueix sense resoldre.
Demostració per ordinador Durant les dècades de 1960 i 1970, el matemàtic alemany Heinrich Heesch va desenvolupar mètodes per utilitzar ordinadors per buscar demostracions. Cal destacar que va ser el primer a utilitzar el mètode de descàrrega per demostrar el teorema, que va resultar ser important en la part inevitable de la posterior demostració d'Appel-Haken. També es va estudiar el concepte de reductibilitat i, juntament amb Ken Durre, va desenvolupar-ne una prova d'ordinador. Desafortunadament, en aquest moment crític, no va poder aconseguir el temps de supercomputació necessari per continuar el seu treball.
Altres matemàtics van continuar a partir dels seus mètodes i del seu enfocament d'utilitzar l'ordinador. Mentre que altres grups de matemàtics competien per aconseguir demostracions completes, Kenneth Appel i Wolfgang Haken, de la Universitat d'Illinois van anunciar, el 21 de juny de 1976, que havien demostrat el teorema. Van rebre l'assistència de John A. Koch en alguna part del treball algorítmic.
Si la conjectura dels quatre colors fos falsa, hi hauria almenys un mapa amb el menor nombre possible de regions que requerís cinc colors. La demostració mostra que aquest contraexemple mínim no pot existir, a través de l'ús de dos conceptes tècnics: Un conjunt inevitable és un conjunt de configuracions tals que cada mapa ha de tenir almenys una configuració d'aquest conjunt. Una configuració reductible és una disposició de països que no pot ocórrer en un contraexemple mínim. Si un mapa conté una configuració reductible, llavors el mapa es pot reduir a un mapa més petit. Aquest mapa més petit té la condició que si es pot acolorir amb quatre colors, llavors el mapa original també pot. Això implica que si el mapa original no es pot acolorir amb quatre colors llavors el mapa més petit tampoc pot, de manera que el mapa original no és mínim.
Utilitzant regles i procediments matemàtics basats en les propietats de les configuracions reductibles, Appel i Haken van trobar un conjunt inevitable de configuracions reductibles, i van demostrar per tant que no podia existir un contraexemple mínim per la conjectura dels quatre colors. La seva demostració va reduir la infinitud de possibles mapes a 1.936 configuracions reductibles (posteriorment van ser reduïts a 1.476), que van haver de ser comprovades una per una per ordinador, cosa que va durar més de mil hores. Aquesta part sobre la reductibilitat del treball va ser comprovada independentment amb programes i ordinadors diferents. No obstant això, la part d'inevitabilitat de la demostració es va verificar en més de 400 pàgines de microfilm, que van haver de ser comprovades a mà.
Els mitjans de comunicació d'arreu del món van difondre àmpliament l'anunci d'Appel i Haken, i el departament de matemàtiques de la Universitat d'Illinois va utilitzar un mata-segells que deia "Amb quatre colors n'hi ha prou". Alhora, el caràcter inusual de la demostració —va ser el primer teorema important que es va demostrar amb una àmplia assistència de l'ordinador— i la complexitat de la part verificable per humans va despertar una gran controvèrsia.