De vierkleurenstelling uitgelegd

In 1852 merkte een jonge wiskundige die een kaart van de graafschappen van Engeland inkleurde op dat vier kleuren genoeg leken om aangrenzende graafschappen van elkaar te onderscheiden. Kon dat voor elke mogelijke kaart gelden? De vraag werd een van de beroemdste problemen van de wiskunde, trok een geroemd maar fout bewijs aan dat elf jaar overeind bleef, en werd uiteindelijk in 1976 beslecht op een manier die veranderde wat wiskundigen als bewijs accepteren.

Een kaart met onregelmatige landen, met vier kleuren zo ingekleurd dat geen twee buren dezelfde kleur hebben
Een kaart met onregelmatige landen, met vier kleuren zo ingekleurd dat geen twee buren dezelfde kleur hebben

De vraag

Francis Guthrie, een oud-student van Augustus De Morgan, vroeg of elke kaart met vier kleuren kan worden ingekleurd zodat landen met een gemeenschappelijke grens verschillende kleuren krijgen. Twee regels maken de vraag precies. Landen moeten samenhangend zijn, elk uit één stuk, en landen die elkaar alleen in één punt raken, tellen niet als buren. Drie kleuren zijn duidelijk niet altijd genoeg, want een land omringd door een ring van drie andere die elkaar allemaal raken, heeft een vierde nodig. De vraag is of er ooit een vijfde nodig is.

Kaarten als grafen

Zet een punt in elk land en trek een lijn tussen twee punten wanneer hun landen een grens delen. Het resultaat is een graaf, en omdat de kaart op een plat vel ligt, kunnen de lijnen zonder kruisingen worden getekend: de graaf is vlak. De kaart inkleuren is de knopen van deze graaf zo kleuren dat de uiteinden van elke kant verschillen. Het kleinste aantal kleuren dat werkt, is het chromatisch getal, en de vierkleurenstelling zegt dat geen enkele vlakke graaf een chromatisch getal boven vier heeft.

Het bewijs van Kempe dat faalde

In 1879 publiceerde de advocaat en wiskundige Alfred Kempe een bewijs. Het slimme idee ervan, nu Kempe-ketens genoemd, is om twee kleuren te verwisselen langs een samenhangende keten van landen om een kleur vrij te maken waar die nodig is. Het bewijs werd elf jaar lang geaccepteerd, tot Percy Heawood in 1890 een gat vond. Heawoods reparatie bewees een zwakker resultaat: vijf kleuren zijn altijd genoeg. Kempes ketens bleven bestaan en werden een hulpmiddel in het uiteindelijke bewijs.

Waarom vijf makkelijk is

Elke vlakke graaf heeft een knoop met hoogstens vijf buren; dat volgt uit de formule van Euler, die een vlakke graaf met n knopen beperkt tot hoogstens 3n − 6 kanten. Verwijder zo'n knoop, kleur de rest van de kaart met hetzelfde argument en zet de knoop terug. Als zijn buren minder dan vijf kleuren gebruiken, is er een vrij. Als ze alle vijf gebruiken, maakt een verwisseling langs een Kempe-keten er altijd een vrij. Met vier kleuren kan dezelfde verwisseling mislukken, en dat is precies het gat dat Kempe over het hoofd zag.

Het computerbewijs

In 1976 bewezen Kenneth Appel en Wolfgang Haken aan de Universiteit van Illinois de stelling. Ze lieten zien dat elke kaart minstens een van 1.936 configuraties uit een onvermijdbare verzameling bevat, en dat elke configuratie reduceerbaar is: een kleinste kaart die vijf kleuren nodig had, zou haar niet kunnen bevatten. Het controleren van de reduceerbaarheid kostte meer dan duizend uur op computers, veel te veel om met de hand te verifiëren. Veel wiskundigen voelden zich ongemakkelijk bij een bewijs dat geen mens volledig kon lezen, en het debat over computerondersteunde bewijzen begon.

Wolfgang Haken, die in 1976 samen met Kenneth Appel aan de University of Illinois de vierkleurenstelling bewees.
Wolfgang Haken, die in 1976 samen met Kenneth Appel aan de University of Illinois de vierkleurenstelling bewees.

Eenvoudiger bewijzen en volledige verificatie

In 1996 publiceerden Neil Robertson, Daniel Sanders, Paul Seymour en Robin Thomas een systematischer bewijs met 633 configuraties, nog steeds door een computer gecontroleerd maar makkelijker te verifiëren. In 2005 formaliseerden Georges Gonthier en Benjamin Werner het hele bewijs in de bewijsassistent Coq, zodat een klein, betrouwbaar programma elke logische stap controleert. Tegenwoordig is de vierkleurenstelling een van de grondigst geverifieerde resultaten in de wiskunde.

Kleuralgoritmen

Een vierkleuring van een gegeven kaart vinden gaat in de praktijk snel, maar het kleinste aantal kleuren voor een algemene graaf vinden is moeilijk: beslissen of drie kleuren volstaan, is NP-volledig. Praktische methoden zijn onder meer gulzig kleuren in volgorde van afnemende graad, DSATUR, dat als volgende de meest beperkte knoop kleurt, en zoeken met backtracking, dat keuzes verkent en ze ongedaan maakt als het vastloopt. Graafkleuring plant examens zonder botsingen, wijst radiofrequenties toe zodat naburige zenders elkaar niet storen, en verdeelt registers in compilers.

Probeer het zelf

Open de kaartkleurder voor de vierkleurenstelling om kaarten van 4 tot 120 landen te maken, kleur ze met de hand in met vier kleuren en zie conflicten in rood verschijnen. Laat gulzig kleuren, DSATUR of backtracking de kaart stap voor stap oplossen, toon de graaf van aangrenzende landen en controleer hoeveel kleuren de kaart echt minimaal nodig heeft.

Veelgestelde vragen

Hebben kaartenmakers iets aan de stelling?

Nauwelijks. Echte kaarten worden voor de duidelijkheid meestal met meer kleuren ingekleurd, en ze bevatten oceanen, meren en landen die uit meerdere stukken bestaan, waar de stelling niet over gaat. Haar belang is wiskundig: ze dreef de ontwikkeling van de grafentheorie aan en riep de vraag op wat als bewijs telt.

Wat is een Kempe-keten?

Neem twee kleuren, zeg rood en blauw, en een rood gekleurd land. De Kempe-keten ervan is de verzameling van alle rode en blauwe landen die je vanuit dat land kunt bereiken door alleen via rode en blauwe buren te stappen. Rood en blauw in de hele keten verwisselen houdt de kleuring geldig en kan een kleur vrijmaken voor een land naast de keten.

Waarom breken landen uit meerdere stukken de stelling?

Als een land mag bestaan uit losse gebieden die allemaal dezelfde kleur moeten hebben, is de burengraaf niet langer vlak, en kunnen er kaarten worden gemaakt die elk aantal kleuren tot 12 nodig hebben bij twee stukken per land, zoals Heawood bestudeerde in zijn imperiumprobleem.

Waarom maakt de kaartkleurder kaarten uit punten?

Elk land is het gebied van het vierkant dat dichter bij één willekeurig punt ligt dan bij elk ander punt, een Voronoi-diagram. Dat geeft realistisch ogende kaarten met convexe landen, en twee landen zijn precies dan buren wanneer hun gebieden een stuk grens delen, wat de app nauwkeurig berekent.

Klaar om het te proberen?

Open PictorX in je browser - geen installatie, geen creditcard nodig om te starten.

Open de kaartkleurder voor de vierkleurenstelling