Geïnspireerd door het artikel ’Vier kleuren volstaan’, zegt de computer – Pythagoras
Neem een kaart van Amerika. Pak vier verschillend gekleurde potloden. Je zult ontdekken dat het mogelijk is om elke staat van Amerika een andere kleur te geven dan zijn buurman. Dit is wat Francis Guthrie deed in 1852. Na het inkleuren van deze kaart kreeg Guthrie ambities. Hij vroeg zich af of het mogelijk was om elke willekeurige landkaart op dezelfde manier in te kleuren zoals hij dat bij de kaart van Amerika had gedaan, slechts met vier kleuren. Dit vraagstuk legde hij voor bij de wiskundige De Morgan, die het probleem vervolgens introduceerde onder wiskundigen. Hiermee was het vierkleurenprobleem geboren.

Gravenprobleem

Het was de wiskundige Tait die in 1880 dit vierkleurenprobleem omzette in een grafenprobleem. Dit deed hij door midden in elk land een punt te zetten en elk paar van aangrenzende landen te verbinden door middel van een lijn, ook wel een rib. Dit zorgde ervoor dat de toen al bestaande grafentheorieën toegepast konden worden op het nieuwe probleem. In de loop der jaren hebben verschillende wiskundigen zich gebogen over deze vierkleurenstelling.

Drielandenpunten

Arthur Cayley was de eerste wiskundige die een artikel gerelateerd aan deze vierkleurenstelling publiceerde. Het artikel was geen bewijs voor de stelling, maar een bewijs dat er slechts gekeken hoefde te worden naar drielandenpunten. De gedachte hierachter is vrij simpel. Neem een punt waarin vier landen aan elkaar grenzen. Wanneer je op dit punt een extra landje plakt, zijn er enkel drielandenpunten over. Deze kaart kan ingekleurd worden met vier kleuren. Wanneer het nieuw gecreëerde landje dan weer ingekrompen wordt tot het oorspronkelijke hoekpunt, is de oorspronkelijke kaart ook in vier kleuren gekleurd. Figuur 1 laat zien hoe dit werkt bij een punt waarin zes landen aan elkaar grenzen.

De Londense advocaat Kempe was in 1879 de eerste die met een bewijs kwam voor de vierkleurenstelling. Helaas werd dit bewijs na elf jaar ongeldig verklaard, toen bleek dat zijn bewijs desastreuze fouten bevatte. Voordat dit bewijs toegelicht kan worden, moet er eerst een aantal aannames en wiskunde begrippen gedefinieerd worden.

Aannames

Bij het vierkleurenprobleem zijn twee landen aangrenzend wanneer ze een gemeenschappelijke grens hebben. Een gemeenschappelijk punt is dus niet voldoende. Daarnaast neemt men aan dat alle landen samenhangend zijn, dat wil zeggen dat ze niet uit meerdere delen bestaan. Tot slot werkt men logischerwijs met enkel planaire grafen. Dit zijn grafen die op een plat vlak zodanig getekend kunnen worden dat de ribben elkaar niet snijden.

Telformule

Volgens de veelvlakkenstelling van de alom bekende wiskundige Euler geldt voor elke samenhangende niet-lege planaire graaf de volgende vergelijking:

Waarbij n het aantal punten (landen) is, m het aantal ribben en f het aantal hoekpunten. Deze stelling kan bewezen worden door middel van inductie.
Als we stellen dat het aantal tweehoeken (een land omsloten door twee ribben) in een kaart c₂ is, het aantal driehoeken c₃ en het aantal k-hoeken c_k (), dan geldt voor het aantal punten:

Het aantal ribben kan gedefinieerd worden in termen van de landen. Een k-hoek levert k ribben en elk van die ribben wordt gedeeld met een buurland. Hierdoor ontstaat de volgende formule voor het aantal ribben:

Daarnaast weten we door de publicatie van Cayley dat we ons slechts hoeven te richten op punten waarbij drie landen samen komen. Daarom geldt ook de volgende vergelijking:

Wanneer we de bovenstaande drie verbanden combineren met de Eulerformule, die aan het begin van alinea genoemd is, ontstaat de zogenaamde telformule:

Onvermijdelijke set en configuratie

Kijkend naar de bovenstaande telformule kunnen we concluderen dat of . Om deze reden wordt de set ook wel een onvermijdelijke set genoemd. Deze zal verderop een belangrijke rol spelen bij de verschillende bewijzen. Een voorbeeld van een onvermijdelijke set is een land met zes buren. Een land of een bepaalde combinatie van landen wordt ook wel een configuratie genoemd.

Manier van bewijzen

Om de vierkleurenstelling te bewijzen, moet de stelling bewezen worden voor elke mogelijke kaart. Toch is er een manier gevonden zodat er enkel naar een eindig aantal gevallen gekeken hoeft te worden. Er wordt dan gebruik gemaakt van een bewijs uit het ongerijmde. Hierbij ga je er van uit dat er kaarten bestaan waarvoor vier kleuren niet voldoende zijn. In dat geval moet er een kleinste tegenvoorbeeld zijn, dit is het tegenvoorbeeld met het kleinste aantal landen. Wanneer er één land weggehaald wordt uit dit kleinste tegenvoorbeeld, zou de vierkleurenstelling weer moeten gelden. Dan blijkt dat na wat gepuzzel ook dat ene extra land één van de vier kleuren kan krijgen en dan geldt de vierkleurenstelling weer. Er is dus sprake van een contradictie.
Het venijn bij deze manier van bewijzen ligt in het verwijderen van dat ene land. Er mag vooraf namelijk niets aangenomen worden, omdat het bewijs voor alle gevallen moet gelden. Dit is waar de onvermijdelijke set komt kijken. Ongeacht de vorm van het kleinste tegenvoorbeeld, bevat hij altijd configuraties uit de onvermijdelijke set. Om de vierkleurenstelling te bewijzen moet men dus elke configuratie langsgaan om aan te tonen dat het mogelijk is om de kaart vier kleuren te geven door de configuratie er eerst uit te halen en deze vervolgens weer toe te voegen. Wanneer dit mogelijk is, dan noemen we die configuratie gereduceerd. Als alle configuraties uit de onvermijdelijke set gereduceerd kunnen worden, dan is het bestaan van tegenvoorbeelden niet mogelijk en kunnen we concluderen dat alle kaarten dus vierkleurbaar zijn.

Kempe

Zoals hierboven al genoemd werd, was de Engelse Kempe de eerste die een bewijs leverde voor de vierkleurenstelling. Zijn methode was als volgt: aanschouw het kleinste tegenvoorbeeld en beschouw de twee-, drie-, vier- of vijfhoeken die er volgens de onvermijdelijke set in moeten zitten. In het geval van twee- en driehoeken liet hij deze verdwijnen, kleurde hij de rest van de kaart in, wat mogelijk was omdat het een kleinste tegenvoorbeeld was, en was er altijd een kleur over om  de twee- of driehoek mee in te kleuren. Deze waren dus reduceerbaar. Met een vierhoek is dit niet mogelijk, omdat deze aangrenst kan worden door vier landen met alle vier een andere kleur. Laat de vier verschillende kleuren rood (r), blauw (b), groen (g) en paars(p) zijn, zoals in figuur 2.

Neem nu de rode en groene landen die aan het rode vlak boven en aan het groene land onder de driehoek zitten. Deze zijn niet met elkaar verbonden, zoals het linkerfiguur van figuur 2, of ze zijn wel verbonden, zoals het rechterfiguur van figuur 2. Indien ze niet verbonden zijn, dan kan elk groene land boven rood gekleurd worden en andersom. De vierhoek heeft dan drie kleuren om zich heen en kan rood gekleurd worden, zoals hieronder in figuur 3 gedaan wordt. Indien ze wel verbonden zijn, dan is er dus een pad, ook wel een Kempe-keten, waarlangs het rode land verbonden is met het groene land eronder. Een kleurverwisseling heeft dan geen zin. Wel is het dan zo dat er geen gesloten weg is tussen het paarse en het blauwe land, dus hier kan wel kleurverwisseling plaatsvinden. Bij de vijfhoek paste Kempe tegelijkertijd twee kleurveranderingen en twee ketens toe, waardoor het aantal aangrenzende kleuren teruggebracht werd tot drie. Dit laatste punt bleek later foutief te zijn, omdat de twee kleurwisselingen niet altijd tegelijkertijd uitgevoerd kunnen worden. Dit werd aangetoond door Heawood in 1890, die door middel van Kempes methode later wel bewees dat elke kaart met in ieder geval vijf kleuren gekleurd kan worden. Daarnaast werd Kempes onderzoekmethode toegepast in latere versies van het bewijs voor de vierkleurenstelling.

Heesch en het ontladen

Heesch pakte het onderzoek weer op in de eerste helft van de twintigste eeuw en kwam met de methode van ontladen, waarmee nieuwe onvermijdelijke sets gevonden konden worden. Neem bijvoorbeeld de onderstaande onvermijdelijke set {tweehoek, driehoek, vierhoek, twee vijfhoeken aan elkaar, een vijf- en zeshoek aan elkaar}. Door middel van ontladen kun je bewijzen dat dit inderdaad een onvermijdelijke set is. Dit gaat als volgt: geef elk land de lading 6 – m, waarbij m het aantal ribben is. Stel dat de bovengenoemde set geen onvermijdelijke set is en bereken vervolgens de lading van de hele kaart. Omdat de bovengenoemde set geen onvermijdelijke set is, kunnen we stellen dat . De lading van de kaart is dan gegeven door:

Waarbij de rechterzijde van het gelijkteken voortkomt uit de telformule. Wanneer je nu de lading van de vijfhoek evenredig over de aanliggende vijf buren verdeelt, blijkt de lading van elke vijfhoek nul te zijn en die van elke zeshoek blijkt ook nul. Die van de zevenhoek wordt ten hoogste , omdat een zevenhoek ten hoogste drie vijfhoekige buren kan hebben. De lading van de totale landkaart zal dus negatief zijn en dus niet gelijk aan 12. Dit is wederom een contradictie en daardoor kan een dergelijke kaart niet bestaan en is deze set inderdaad onvermijdelijk.
Wanneer Heesch een onvermijdelijke set gevonden had, probeerde hij de configuraties te reduceren. Lukte dit niet, dan paste hij zijn ontladingstheorie aan, zodat er een grotere onvermijdelijke set ontstond, waarbij het probleem opgelost was. Begin jaren ‘70 had Heesch een onvermijdelijke set van 8904 configuraties, die naar eigen mening reduceerbaar moesten zijn. Helaas kreeg Heesch het geld niet bij elkaar om zijn standpunt te kunnen verifiëren, dus weten we nu nog steeds niet of alle 8904 configuraties van zijn onvermijdelijke set te reduceren zijn.

Haken en Appel

Het waren de wiskundigen Haken en Appel die uiteindelijk het eerste bewijs voor het vierkleurenprobleem leverden. Zij hadden een onvermijdelijke set bestaande uit 1936 configuraties. Om de onvermijdelijkheid van hun configuraties te bewijzen, gebruikten zij een ontladingsalgoritme met 487 verschillende gevallen. Bij het vinden van de set hebben zij intensief gebruik gemaakt van een computer. Het bewijs van de onvermijdelijkheid ging echter wel met de hand. Het tweede gedeelte van het bewijs, de reductie van de 1936 configuratie, was onmogelijk met de hand uit te voeren of te controleren; een computer heeft 1200 uur gerekend met een uitdraai bestaande uit een stapel papier van meer dan een meter hoog.

Tweede bewijs

In 1994 kwamen vier wetenschappers Neil Robertson, Paul Seymour, Daniel Sanders en Robin Thomas met een tweede bewijs. Oorspronkelijk was het de bedoeling dat deze vier wiskundigen het bewijs van Haken en Appel wilden vaststellen, maar toen ze daarbij vastliepen, besloten ze een eigen bewijs uit te voeren. Hun onvermijdelijke set bevat slechts 633 configuraties en hun ontladingsalgoritme telt maar 32 regels. Daarnaast is hun programma beschikbaar op internet, zodat ook anderen de berekeningen kunnen herhalen.

Wel of geen bewijs?

Met de twee bewijzen van ‘Haken en Appel’ en van ‘Robertson et al.’, is er een discussie losgebarsten in de wereld der wiskundigen. Is dit wel een geldig wiskundig bewijs? Tegenstanders zeggen dat computerbewijzen niet volgens de regels van een wiskundig bewijs zijn. Wiskundige bewijzen zouden zich onderscheiden van onder andere natuurkundige bewijzen, omdat wiskundigen alleen conclusies trekken wanneer er sprake is van absolute zekerheid op basis van een waterdicht bewijs, terwijl natuurkundigen algemene conclusies trekken uit een serie experimenten. Dit geleverde bewijs was door niemand te begrijpen of zelfs te lezen, ook door de makers zelf niet. De enige manier om het te controleren is door middel van een computer. En dat, zo stellen de tegenstanders, is niet de manier waarop wiskundigen stellingen bewijzen. Het is meer een experiment. Voorstanders van het computerbewijs beweren dat ook de klassieke bewijzen door veel mensen niet te lezen zijn en dat bij computerbewijzen bovenal aanzienlijk minder fouten worden gemaakt dan bij menselijke bewijzen. Het antwoord op de vraag of de vierkleurenstelling inmiddels bewezen is, hangt dus volledig af van de visie op het bewijs.
 
Wat is het nut van deze probleemstelling, zullen velen zich afvragen. Er zijn immers weinig mensen die zoals Guthrie in hun vrije tijd landkaarten inkleuren. De vierkleurenstelling heeft echter vele toepassingen. Denk bijvoorbeeld aan het vervoeren van circusdieren. Je hebt hierbij de vierkleurenstelling nodig wanneer je wilt voorkomen dat twee dieren in dezelfde wagen worden geplaatst en elkaar op zullen eten, terwijl je ook het aantal wagens wilt minimaliseren. Of neem de licenties voor frequenties voor radiozenders. Je wilt zo min mogelijk frequenties toewijzen, maar er tegelijkertijd voor zorgen dat radiostations die te dicht bij elkaar zitten niet gaan storen en op verschillende frequenties zitten. Of neem tot slot reserveringen van een bungalowhuisje. De eigenaar van de bungalows wil de mensen zodanig over de huisjes verdelen, dat de periodes niet overlappen, maar het aantal huisjes in gebruik geminimaliseerd wordt. Kortom, weer een abstract wiskundig probleem waarvan de oplossing zeer nuttig blijkt te zijn in de praktijk!

Dit artikel is geschreven door Wies van Eeden en verscheen in GAXEX 1 van jaargang 35.
Wies was actief als redacteur voor de GAXEX van september 2010 tot medio 2014.