Guthriea capensis i Erica Guthriei són dues plantes sud-africanes anomenades així en honor de Francis Guthrie, un excel.lent botànic afeccionat i advocat que estudià al College de Londres.  F. Guthrie també té un lloc a la història de les matemàtiques com a formulador d’un dels problemes més famosos: el problema dels quatre colors. El 1852, tot just acabats els seus estudis al College, Francis Guthrie escrigué al seu germà Frederick assenyalant-li que, segons el seu parer, qualsevol mapa que es pugui dibuixar en un full de paper es pot acolorir amb només quatre colors de forma que, com és usual, regions frontereres tinguin colors diferents. Preguntava si era possible trobar una demostració d’aquest fet. Frederick no ho va saber provar i va preguntar al matemàtic Augustus de Morgan, professor seu. De Morgan tampoc no trobà resposta, però el problema l’intrigà vivament i mirà d’interessar altres matemàtics, sigui verbalment, sigui per carta o fent-ne referència a publicacions.

Precisem el problema. En els mapes polítics pot ocórrer que un mateix estat ocupi dues regions no frontereres. Per exemple, l’estat de Michigan als Estats Units d’Amèrica està partit en dues regions separades. Si admetem que les dues regions han de tenir el mateix color, aleshores és fàcil pensar un mapa que requereixi cinc colors. La figura 1 (a) n’és un exemple:  L’estat A està en dues parts disjuntes i així  cada estat  té frontera amb els altres quatre. Per tant, cada dos estats han de tenir diferent color. Calen, doncs, cinc colors.

Si dues regions que tenen la frontera reduïda a un únic punt han de tenir diferent color, aleshores hi ha mapes que requereixen tants colors com es vulgui: només cal prendre’ls en forma de pastís.  Per exemple la figura 2 (a) és un exemple de mapa que requereix sis colors perquè cada regió és adjacent a les altres cinc.

En les coloracions a què fa  referència el problema de Gurthrie, regions no frontereres es poden acolorir amb el mateix color i regions que tenen un únic punt en comú també. Amb aquestes condicions, els mapes de les figures 1(a)  i 1(b) es poden acolorir amb només quatre colors, com mostren les figures 1(b) i 2 (b).  A més, aquests són exemples de mapes que no es poden acolorir amb menys de quatre colors. El que resulta sorprenent és que, com afirmava Guthrie, per complicat que sigui un mapa es pugui pintar amb només quatre colors. El problema consistia en demostrar que quatre colors són suficients per a qualsevol mapa o bé en trobar-ne un que en requereixi cinc o més.

La major part de demostracions errònies es basen en el convenciment que el nombre mínim de colors que cal per pintar un mapa és el màxim nombre de regions dos a dos adjacents. Després es prova que en cap mapa no hi pot haver cinc regions tals que cadascuna sigui adjacent a les altres quatre, un resultat que ja era conegut per De Morgan. La conclusió és immediata: quatre colors són suficients per a qualsevol mapa. Malauradament, la hipòtesi de partida és falsa, com prova el mapa de la figura 3. En aquest mapa el nombre màxim de regions mútuament adjacents és tres, però requereix quatre colors, tres per a les regions de la corona i un altre per a la central.

D’entre els matemàtics als qui arribà el problema a través de De Morgan,  uns, com William  R.Hamilton, no li dedicaren massa atenció, i altres, com Arthur Cayley, s’encuriosiren ràpidament. Probablement una publicació de Cayley del 1879 als Proceedings de la Royal Geographical Society explicant la dificultat del problema fou el punt d’inflexió en la seva popularització. Pocs mesos després, Alfred Bray Kempe, que havia estat estudiant de Cayley, anuncià que tenia la demostració. La prova de Kempe aparegué el 1879 a l’American Journal of Mathematics. El problema semblava resolt: es podia canviar el nom de problema dels quatre colors pel de teorema dels quatre colors.

La demostració es donà per bona durant 11 anys fins que el 1890, Percy John Heawood féu notar un error en l’argumentació de Kempe i, a més, mostrà que l’errada difícilment es podria  arranjar.  Hi tornava a haver problema.  A partir d’aquí els esforços es van succeir. Tot i que la prova de Kempe no resultà definitiva, les seves tècniques eren valuoses i diferents matemàtics, entre els que cal citar G.D. Birkhoff, P. Franklin i H. Heesh, treballaren per millorar-les. Tot i així, cap a 1950 només s’havia provat que tot mapa amb menys de 36 regions es pot acolorir amb 4 colors.

Una altra possibilitat s’obria a la dècada dels 30 amb els resultats cabdals sobre fonaments de les matemàtiques.  Kurt Gödel demostrà que en tot sistema lògic que permeti la construcció dels nombres naturals, el que es considera el mínim indispensable per fer matemàtiques, hi ha enunciats tals que, dins del sistema, no es pot demostrar ni que siguin certs ni que siguin falsos. Calia considerar la poc engrescadora possibilitat que alguns problemes històrics, com el de Fermat o el dels quatre colors, fossin d’aquesta mena. Per als matemàtics això era probablement el pitjor que podia passar. Sortosament, no ha estat així.

Cap a 1970, els intents de demostrar el  problema dels quatre colors ja havien  produït notoris resultats en diferents branques de les matemàtiques, però no la desitjada demostració. Després d’un segle llarg d’esforços, l’escepticisme respecte a la possibilitat de sortir-se’n era natural. El 1972 Kenneth Appel i Wolfgang Haken, s’abocaren al problema amb tot el bagatge de coneixements i tècniques acumulats i una eina molt més nova: l’ordinador.  La teoria coneguda afegida a la que ells mateixos van desenvolupar va permetre reduir l’estudi a un nombre molt gran de casos, impossible d’estudiar a mà però possible d’estudiar exhaustivament amb l’ajuda dels programes adequats, que hagueren de dissenyar i escriure. Més de 1.200 hores de funcionament d’ordinador acabaren la tasca. En dos articles de l’Illinois J. Math. publicats els anys 1977, el primer signat per Appel i Hankel i el segon per Appel, Hankel i J. Koch, donaren compte de la suficiència de quatre colors. L’ús sense precedents dels ordinadors per demostrar un resultat teòric posà en qüestió el que fins al moment s’entenia per demostració matemàtica i obrí un debat que, potser menys viu, encara perdura. Des del 1977 s’han trobat diversos errors a la prova d’Appel i Hankel, però la singularitat de la seva demostració, que inclou programes autocorrectors, ha permès corregir-los. L’any 1989 Appel i Hankel publicaren una nova versió amb tots els errors coneguts corregits. Al Congrés Internacional de Matemàtiques celebrat a Zürich el 1994, Paul D. Seymour presentà una prova simplificada del teorema dels quatre colors obtinguda amb col.laboració de Neil Robertson, Daniel P. Sanders i Robin Thomas. Tot i que el nou plantejament no evita l’ús d’ordinadors, redueix la quantitat d’operacions a un nivell molt més tolerable, de forma que els qui entenen els fonaments teòrics del plantejament poden duplicar la prova en mig dia. La qüestió de si existeix una prova lliure de computació segueix, però, oberta.

Quines són les característiques d’aquest problema, que l’han fet tan especial? Primer, que l’enunciat del problema és molt simple, intel.ligible per a tothom.  Segon, que ràpidament s’arriba a la certesa que, en efecte, quatre colors són suficients. Des de Francis Guthrie fins a Appel i Hankel, el convenciment general va ser  que amb quatre colors n’hi havia prou. Tots els exemples coneguts ho avalaven. En qualsevol altre camp del coneixement la immensa evidència pràctica hagués estat considerada definitiva. En matemàtiques, no. En matemàtiques  calia una demostració, calia saber per què. Tercer, la seva dificultat, que el va convertir en un repte per a molts matemàtics de primera línia. En quart lloc, el desenvolupament que ha significat per a moltes parts de la matemàtica, per exemple per a la teoria de grafs, on el problema ha estat un autèntic motor generador de matemàtiques, amb profunds resultats teòrics i insospitades aplicacions. Finalment, una demostració molt poc convencional que posa damunt la taula l’ús sistemàtic d’ordinadors en la demostració de teoremes.
 

Bibliografia

[1]  Kenneth Appel and Wolfgang Haken: La solución del problema del mapa de cuatro colores, Investigación y ciencia, Diciembre de 1977,  78—90.

En aquest article de caire divulgatiu, els autors de la demostració fan un repàs històric i expliquen sense tecnicismes el plantejament general de la seva prova.

[2] Rudolf Fritsch and Gerda Fritsch: The Four-Color Theorem. Springer, New York, (1991).

El primer capítol d’aquest llibre conté breus biografies dels personatges més importants relacionats amb el problema i una descripció de les seves contribucions. La resta  presenta matemàticament els aspectes topològics i combinatorics del problema amb la intenció de posar a l’abast d’estudiants i professors les tècniques emprades, incloses les del mètode Seymour. A la bibliografia apareixen les publicacions més rellevants relacionades amb el tema.

[3] Thomas L. Saaty and Paul C. Kainen: The Four-Color Problem. Assaults and Conquest. Dover Publications, Inc., New York (1986).

Aquest és un llibre de teoria de grafs escrit entorn del problema dels quatre colors. Hi podeu trobar formulacions equivalents, variacions i generalitzacions del problema, etc., així com una extensa bibliografia.
 

Text: Josep Maria Brunat
Disseny gràfic: Sergi Lario