Usuari:Habicht/proves/Teorema dels quatre colors

A partir de en:Four color theorem

Exemple d'un mapa de quatre colors.

Mapa del món acolorit de color verd, groc, blau i vermell.

Un mapa de quatre colors dels estats dels Estats Units (sense tenir en compte els llacs).

Mapa administratiu de Rússia acolorit amb quatre colors

En matemàtiques, el teorema dels quatre colors estableix que, en qualsevol separació 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

Teorema dels quatre colors Quasevol mapa geogràfic amb regions contigües es pot acolorir amb quatre colors diferents, de tal manera que no hi hagi regions adjacents amb el mateix color.

Exemple d'un mapa de l'Azerbaidjan amb regions no contigües.

Per a que 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:

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 composé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.

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 creuaments 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:

Teorema dels quatre colors Qualsevol graf planar és 4-colorable.

O equivalentment:

Teorema dels quatre colors Si $G\,$ és un graf pla, llavors $\chi (G)\leq 4$,

on $\chi (G)$ és el nombre cromàtic del graf $G$.

Història

Intents de demostració inicials

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'ex-supervisor 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:

«

(anglès) A student of mine [Guthrie] asked me to day to give him a reason for a fact which I did not know was a fact — and do not yet. He says that if a figure be any how divided and the compartments differently coloured so that figures with any portion of common boundary line are differently coloured — four colours may be wanted but not more — the following is his case in which four colours are wanted. Query cannot a necessity for five or more be invented...

(català) Un dels meus estudiants [Guthrie] m'ha demanat avui de donar-li una raó a un fet que jo no sabia que fos un fet —i que encara ara no ho sé. Diu que si una figura sigui dividida de qualsevol forma i els compartiments acolorits d'un color diferent de tal manera que les figures que comparteixin qualsevol part de frontera comuna siguin d'un color diferent, llavors es poden necessitar quatre colors, però no més. El que segueix és el seu cas en el qual es necessiten quatre colors. Busca que no es pugui inventar una necessitat per a cinc o més...

»

"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.

«	(anglès) This arises in the following way. We never need four colours in a neighbourhood unless there be four counties, each of which has boundary lines in common with each of the other three. Such a thing cannot happen with four areas unless one or more of them be inclosed by the rest; and the colour used for the inclosed county is thus set free to go on with. Now this principle, that four areas cannot each have common boundary with all the other three without inclosure, is not, we fully believe, capable of demonstration upon anything more evident and more elementary; it must stand as a postulate.	(català) Això sorgeix de la següent manera. Mai necessitem quatre colors en un barri llevat que hi hagi quatre comtats, cadascun dels quals té fronteres en comú amb cadascun dels altres tres. Una cosa així no pot passar amb quatre àrees llevat que una o més d'elles estiguin envoltades per la resa; i el color utilitzat per al comtat tancat és per tant lliure. Ara bé, aquest principi, que quatre zones que no poden tenir cada una frontera comuna amb totes les altres tres sense estar encerclades, no és, estem plenament convençuts, capaç de ser demostrada a partir de res més evident i més elemental; s'ha de presentar com un postulat.	»
— Augustus De Morgan, The Philosophy of Discovery, Chapters Historical and Critical

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 el 1890 que Percy 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 l 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 en 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 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:

1. Un conjunt inevitable és un conjunt de configuracions tals que cada mapa ha de tenir almenys una configuració d'aquest conjunt.
2. 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 verificable per humans va despertar una gran controvèrsia.

A principis de la dècada de 1980, es van difondre rumors d'un error en la demostració d'Appel-Haken. Ulrich Schmidt, de la Universitat Tècnica d'Aquisgrà, va examinar la demostració d'Appel i Haken com a tema de la seva tesi de màster. Havia comprovat un 40% de la part sobre la inevitabilitat i havia trobat un error significatiu en el procediment de descàrrega. El 1986, l'editor de la revista The Mathematical Intelligencer va demanar a Appel i Haken que escrivissin un article sobre els rumors d'errors en la seva demostració. Ells van respondre que els rumors eren causats per una "mala interpretació dels resultats [d'Schmidt]" i van correspondre amb un detallat article. La seva obra magna, Tots els mapes planars són 4-colorables (anglès: Every Planar Map is Four-Colorable), un llibre que al·legava contenir una demostració completa i detallada (amb un suplement de microfilm de més de 400 pàgines), va aparèixer el 1989 i explicava el descobriment d'Schmidt i diversos errors addicionals trobats per altres.

Simplificació i verificació

Des de la demostració del teorema, s'han trobat algoritmes eficients que acoloreixen mapes amb 4 colors i quereixen només un temps O(n²), on n és el nombre de vèrtexs. El 1996, Neil Robertson, Daniel P. Sanders, Paul Seymour i Robin Thomas van crear un algoritme de temps quadràtic, millorant un algoritme quàrtic basat en la demostració d'Appel i Haken. Aquesta nova demostració és similar a la d'Appel i Haken però més eficient, ja que redueix la complexitat del problema i requereix la comprovació de només 633 configuracions reductibles. Tant les parts d'inevitabilitat com de reducibilitat d'aquesta nova prova han de ser executades per ordinador i no és factible comprovar-es a mà. El 2001, els mateixos autors van anunciar una demostració alternativa, en demostrar el teorema Snark.

El 2005, Benjamin Werner i Georges Gonthier van formalitzar una demostració del teorema dins de l'assistent de proves Coq. Això elimina la necessitat de confiar en els diversos programes d'ordinador utilitzats per verificar els casos particulars; només cal confiar en el nucli de Coq.

Resum de les idees de la demostració

La següent discussió és un resum basat en la introducció del llibre d'Appel i Haken Tots els mapes plans són 4-colorables (anglès: Every Planar Map is Four Colorable). Encara que amb errors, la suposada demostració original de Kempe del teorema dels quatre colors va proporcionar algunes de les eines bàsiques utilitzades més tard per demostrar-lo. L'explicació d'aquesta secció s'ha reformulat en termes de la teoria de grafs moderna.

L'argument de Kempe és el següent. En primer lloc, si les regions planes separades pel graf no estan triangulades (és a dir, no tenen exactament tres arestes en els seus límits), podem afegir arestes sense introduir nous vèrtexs i fer que cada regió sigui triangular, incloent la regió externa. Si aquest graf triangular és colorable amb quatre colors o menys, també ho és el graf original, ja que el mateix acoloriment és vàlid si s'eliminen les arestes que s'havien afegit. Així que per a demostrar el teorema dels quatre colors per a tots els grafs plans és suficient demostrar-lo per a grafs triangulats, i sense pèrdua de generalitat podem assumir que el graf és triangulat.

Suposem que v, e, i f són el nombre de vèrtexs, arestes i regions (cares). Atès que cada regió és triangular i cada aresta és compartida per dues regions, trobem que 2e = 3f. Això, juntament amb la relació d'Euler v - e + f = 2, es pot utilitzar per demostrar que 6v - 2e = 12. Ara, el grau d'un vèrtex és el nombre d'arestes que hi incideixen. Si v_n és el nombre de vèrtexs de grau n i D és el grau màxim de qualsevol vèrtex, llavors

$6v-2e=6\sum _{i=1}^{D}v_{i}-\sum _{i=1}^{D}iv_{i}=\sum _{i=1}^{D}(6-i)v_{i}=12.$

Però com que 12 > 0 i 6 - i ≤ 0 per a tot i ≥ 6, això demostra que hi ha almenys un vèrtex de grau 5 o menys.

Si hi ha un graf que requereix 5 colors, llavors hi ha un graf mínim que requereix 5 colors, tal que l'eliminació de qualsevol dels seus vèrtexs fa que sigui de 4-colorable. Anomenem aquest graf G. G no pot tenir un vèrtex de grau 3 o menys, perquè si d(v) ≤ 3, aleshores podríem eliminar v de G, acolorir el nou graf amb quatre colors, i a continuació afegir de nou v i ampliar l'acoloriment amb 4 colors al graf original escoll per a v un colors diferent del dels seus veïns.

Kempe també va demostrar correctament que G no pot tenir cap vèrtex de grau 4. Igual que abans, eliminem el vèrtex v i acolirim els vèrtexs restants amb quatre colors. Si els quatre veïns de v són de diferents colors, per exemple vermell, verd, blau i groc en sentit horari, busquem una ruta alterna de vèrtexs de color vermell i blau que uneixin els veïns vermell i blau. Aquest camí s'anomena una cadena de Kempe. Hi pot haver una cadena de Kempe que uneixi els veïns vermell i blau, i hi pot haver una cadena de Kempe que uneixi els veïns verd i groc, però no poden existir les dues cadenes simultàniament, ja que aquests dos camins s'haurien de creuar necessàriament, i el vèrtex on es creuen no es podria acolorir. Suposem que són els veïns vermell i blau que no estan encadenats entre si. Explorem tots els vèrtexs connectats al veí vermell per camins alterns vermell-blau i, a continuació, invertim els colors vermell i blau en tots aquests vèrtexs. El resultat segueix sent una coloració de quatre colors vàlida, i ara podem afegir v de nou i acolorir-lo de color vermell.

Això deixa només el cas en què G té un vèrtex de grau 5; però l'argumentació de Kempe era defectuosa en aquest cas. Heawood es va adonar de l'error de Kempe i també va observar que si un estava satisfet amb la demostració segons la qual només es necessiten cinc colors, es podia seguir l'argumentació anterior (canviant només que el contraexemple mínim necessita 6 colors) i utilitzar cadenes de Kempe en la situació d'un vèrtex de grau 5 per demostrar el teorema dels cinc colors.

En qualsevol cas, per fer front a aquest cas d'un vèrtex de grau 5 cal una noció més complicada que la simple eliminació d'un vèrtex. Més aviat, la forma de l'argument es generalitza considerant configuracions, que són subgrafs de G connexos amb el grau de cada vèrtex (en G) especificat. Per exemple, el cas descrit en la situació del vèrtex de grau 4 és la configuració que consta d'un sol vèrtex etiquetat com a grau 4 en G. Com abans, és suficient demostrar que si s'elimina la configuració i el graf restant és 4-colorable, aleshores es pot modificar la coloració de tal manera que quan es torna a afegir la configuració la 4-coloració es pot estendre també al graf G. Una configuració per la qual això és possible s'anomena una configuració reductible. Si d'un conjunt de configuracions n'hi ha almenys una que ha d'ocórrer forçosament en algun lloc de G, aquest conjunt s'anomena inevitable. L'argument anterior va començar donant un conjunt inevitable de cinc configuracions (un sol vèrtex amb grau 1, un sol vèrtex amb grau 2,..., un sol vèrtex amb grau 5) i després es va procedir a demostrar que els primers 4 són reductibles; mostrar un conjunt inevitable de configuracions en el qual totes les configuracions són reductibles equivaldria a demostrar el teorema.

Com que G és triangular, es coneix el grau de cada vèrtex en una determinada configuració, i es coneixen també totes les arestes internes de la configuració, el nombre de vèrtexs de G adjacents a una configuració donada és fix, i estan units en un cicle. Aquests vèrtexs formen l'anell de la configuració; una configuració amb k vèrtexs en el seu anell és una k-anell configuració, i la configuració juntament amb el seu anell s'anomena la configuració anellada. Com en els casos anteriorment indicats, es poden enumerar totes les diferents 4-coloracions de l'anell; qualsevol coloració que es pugui estendre sense modificació a una coloració de la configuració s'anomena inicialment bona. Per exemple, la configuració anterior d'un sol vèrtex amb 3 o menys veïns era inicialment bona. En general, el graf que l'envolta ha de ser sistemàticament reacolorit per convertir la coloració de l'anell en una coloració bona, com en el cas anterior de 4 veïns; en una configuració general amb un anell més gran, això requereix tècniques més complexes. A causa de la gran quantitat de 4-coloracions diferents de l'anell, aquest és el pas principal que requereix ajuda de l'ordinador.

Finalment, queda per identificar un conjunt inevitable de configuracions susceptibles de reducció amb aquest procediment. El principal mètode utilitzat per descobrir un conjunt d'aquest tipus és el mètode de descàrrega. La idea intuïtiva subjacent al mètode de descàrrega consisteix en considerar el graf pla com una xarxa elèctrica. Inicialment, es distribueix una "càrrega elèctrica" entre els vèrtexs de tal manera que el total sigui positiu.

Recordem la fórmula anterior:

$\sum _{i=1}^{D}(6-i)v_{i}=12.$:$\sum _{i=1}^{D}(6-i)v_{i}=12.$

A cada vèrtex se li assigna una càrrega inicial de 6 -d(v). Llavors, es fa "fluir" la càrrega a través de redistribuir-la sistemàticament des d'un vèrtex als seus vèrtexs veïns d'acord amb un conjunt de normes: el procediment de descàrrega. Atès que la càrrega es conserva, alguns vèrtexs segueixen tenint càrrega positiva. Les normes restringeixen les possibilitats de configuracions de vèrtexs amb càrrega positiva, de manera que l'enumeració de totes aquestes configuracions possibles dóna un conjunt inevitable.

Mentre algun element del conjunt inevitable no sigui reductible, es modifica el procediment de descàrrega per tal d'eliminar-lo (alhora que s'introdueixen altres configuracions). El procediment de descàrrega final d'Appel i Haken tenia una gran complexitat i, juntament amb una descripció del conjunt de configuracions inevitable resultant, omplia un volum de 400 pàgines, però es podia comprovar mecànicament que les configuracions que generava eren reductible. La verificació per experts del volum que descriu el conjunt de configuracions inevitable va durar diversos anys.

Un detall tècnic que no s'ha discutit aquí, però que es necessita per completar la demostració, és la reductibilitat d'immersió.

Refutacions falses

El teorema dels quatre colors ha atret un gran nombre de demostracions i refutacions falses en la seva llarga història. Inicialment, The New York Times es va negar a informar sobre la demostració d'Appel-Haken per un tema de política, per por que la demostració resultés ser falsa com les anteriors. Algunes suposades demostracions, com la de Kempe i la de Tait esmentades anteriorment, van estar sota l'escrutini públic durant més d'una dècada abans de ser exposades. Però moltes més, escrit per aficionats, ni tan sols es van arribar a publicar mai.

El mapa (a l'esquerra) s'ha acolorit amb cinc colors, i cal canviar almenys quatre de les deu regions per obtenir una coloració amb només quatre colors (dreta).

En general, els contraexemples més simples (encara que invàlids) intenten crear una regió que toqui totes les altres regions. Això força que les altres regions s'hagin d'acolorir amb només tres colors. Com que el teorema dels quatre colors és cert, això sempre és possible; tanmateix, com que la persona que dibuixa el mapa se centra en la regió gran, no s'adona que les regions restants es poden de fet acolorir amb tres colors.

Aquest truc es pot generalitzar: hi ha molts mapes en què si se seleccionen els colors d'algunes regions per endavant, es fa impossible acolorir les altres regions sense excedir els quatre colors. Un verificador casual del contraexemple pot no pensar en canviar els colors d'aquestes regions, de manera que el contraexemple apareixerà com a vàlid.

Potser un dels efectes que subjau a aquest error comú és el fet que la restricció de color no és transitiva: una regió només s'ha d'acolorir d'un color diferent de les regions que toca directament, no de les regions que toquen les regions que la primera toca. Si aquesta fos la restricció, els grafs plans requeririen un nombre arbitràriament gran de colors.

Altres refutacions falses violen els supòsits del teorema de maneres inesperades, com l'ús d'una regió que consisteix en múltiples parts desconnectades, o prohibint regions del mateix color que es toquin en un punt.

Generalitzacions

En unir-se les fletxes individuals entre elles i les fletxes dobles entre elles, s'obté un tor amb set regions que es toquen mútuament; per tant, són necessaris set colors.

Aquesta construcció mostra el tor dividit en un màxim de set regions, cadascuna de les quals toca totes les altres.

El teorema dels quatre colors s'aplica no només a grafs plans finits, sinó també a grafs infinits que es poden dibuixar sense creuar-se en el pla, i de manera encara més general, a grafs infinits (possiblement amb un nombre incomptable de vèrtexs) per als quals cada subgraf finit és pla. Per demostrar això, es pot combinar la demostració del teorema per a grafs plans finits amb el teorema de De Bruijn–Erdős, que diu que si cada subgraf finit d'un graf infinit és k-colorable, llavors tot el graf és també k-colorable. Això es pot veure també com una conseqüència immediata del teorema de compacitat de Kurt Gödel en Lògica de primer ordre, expressant la coloració d'un graf infinit com un conjunt de fórmules lògiques.

Hom pot considerar també el problema de coloració en superfícies que no siguin el pla. El problema en l'esfera o el cilindre és equivalent al del pla. Per superfícies tancades (orientables o no) amb gènere positiu, el nombre p màxim de colors necessaris depèn de la característica d'Euler χ de la superfície d'acord amb la fórmula

$p=\left\lfloor {\frac {7+{\sqrt {49-24\chi }}}{2}}\right\rfloor ,$

on les claus exteriors denoten la funció sòl.

Alternativament, per a una superfície orientable la fórmula es pot expressar en termes del gènere d'una superfície, g:

$p=\left\lfloor {\frac {7+{\sqrt {1+48g}}}{2}}\right\rfloor$

Aquesta fórmula, anomenada la conjectura de Heawood, va ser conjecturada per Pearcy John Heawood el 1890 i demostrada per Gerhard Ringel i J. T. W. Youngs el 1968. L'única excepció a la fórmula és l'ampolla de Klein, que té característica d'Euler 0 (i per tant la fórmula dóna p = 7) i requereix 6 colors, com va demostrar P. Franklin el 1934.

Per exemple, el tor té característica d'Euler χ = 0 (i gènere g = 1) i per tant p = 7, així que es necessiten com a màxim 7 colors per acolorir qualsevol mapa en un tor. El poliedre de Szilassi és un exemple que necessita set colors.

Una cinta de Möbius necessita sis colors, així com els grafs 1-plans (grafs dibuixats amb un creuament senzill per tall com a màxim). Si s'acoloreixen tant els vèrtexs com les cares d'un graf pla, de manera que no hi ha dos vèrtexs adjacents, cares, o parells de vèrtexs i cares que tinguin el mateix color, es necessiten de nou un màxim de sis colors.{{sfn|Borodin|1984

No hi ha cap extensió òbvia del resultat de coloració per regions sòlides tridimensionals. Mitjançant l'ús d'un conjunt de n varetes flexibles, es pot fer que cada vareta toqui les altres varetes. El conjunt requeriria llavors n colors, o n+1 si es té en compte l'espai buit que també toca a cada vareta. El nombre n pot ser un enter tan gran com es vulgui. Fredrick Guthrie coneixia ja aquests exemples el 1880. Fins i tot per cuboides d'eixos paral·lels (que es consideren adjacents quan dos cuboides comparteixen una àrea límit de dues dimensions) es poden necessitar un nombre il·limitat de colors.

Bibliografia

• Appel, Kenneth; Haken, Wolfgang «Every Planar Map is Four Colorable Part I. Discharging». Illinois Journal of Mathematics, 21, 1977, pàg. 429–490.
• Appel, Kenneth; Haken, Wolfgang; Koch, John «Every Planar Map is Four Colorable Part II. Reducibility». Illinois Journal of Mathematics, 21, 1977, pàg. 491–567.
• Appel, Kenneth; Haken, Wolfgang «Solution of the Four Color Map Problem». Scientific American, 237, 10-1977, pàg. 108–121. DOI: 10.1038/scientificamerican1077-108.
• Appel, Kenneth; Haken, Wolfgang. Every Planar Map is Four-Colorable. Providence, RI: American Mathematical Society, 1989. ISBN 0-8218-5103-9. 
• Borodin, O. V. «Solution of the Ringel problem on vertex-face coloring of planar graphs and coloring of 1-planar graphs». Metody Diskretnogo Analiza, 41, 1984, pàg. 12–26, 108..
• Cayley, Arthur «On the colourings of maps». Proceedings of the Royal Geographical Society of London. Blackwell Publishing, 1, 4, 1879, pàg. 259–261. DOI: 10.2307/1799998. JSTOR: 1799998.
• Gonthier, Georges «Formal Proof—The Four-Color Theorem». Notices of the American Mathematical Society, 55, 11, 2008, pàg. 1382–1393.
• Hadwiger, Hugo «Über eine Klassifikation der Streckenkomplexe». Vierteljschr. Naturforsch. Ges. [Zürich], 88, 1943, pàg. 133–143.
• Heawood, Percy John «Map-Colour Theorem». Quarterly Journal of Mathematics [Oxford], 24, 1890, pàg. 332–338.
• Magnant, C.; Martin, D. M. «Coloring rectangular blocks in 3-space». Discussiones Mathematicae Graph Theory, 31, 1, 2011, pàg. 161–170.
• Nash-Williams, C. St. J. A. «Infinite graphs—a survey». J. Combinatorial Theory, 3, 1967, pàg. 286–301.
• Pegg, Ed, Jr.; Melendez, J.; Berenguer, R.; Sendra, J. R.; Hernandez, A.; Del Pino, J. «Book Review: The Colossal Book of Mathematics». Notices of the American Mathematical Society, 49, 9, 2002, pàg. 1084–1086. Bibcode: 2002ITED...49.1084A. DOI: 10.1109/TED.2002.1003756.
• Reed, Bruce; Allwright, David «Painting the office». Mathematics-in-Industry Case Studies, 1, 2008, pàg. 1–8.
• Robertson, Neil; Sanders, Daniel P.; Seymour, Paul; Thomas, Robin «Efficiently four-coloring planar graphs». STOC'96: Proceedings of the twenty-eighth annual ACM symposium on Theory of computing. ACM Press, 1996, pàg. 571–575. DOI: 10.1145/237814.238005.
• Swart, Edward R. «The philosophical implications of the four-color problem». American Mathematical Monthly. Mathematical Association of America, 87, 9, 1980, pàg. 697–702. DOI: 10.2307/2321855. JSTOR: 2321855.
• Thomas, Robin. The Four Color Theorem, 1995. 
• Thomas, Robin «An Update on the Four-Color Theorem». Notices of the American Mathematical Society, 45, 7, 1998, pàg. 848–859.
• Wilson, Robin. Four Colors Suffice (en anglès). Londres: Penguin Books, 2002. ISBN 0-691-11533-8.