Vierkleurenstelling

De vierkleurenstelling is de stelling in de wiskunde dat het mogelijk is elke willekeurige landkaart waarin de landen elk een geheel vormen, dus zonder exclaves, met behulp van slechts vier kleuren zo in te kleuren dat geen twee aangrenzende landen dezelfde kleur krijgen. Twee landen gelden hierbij als aangrenzend als ze een stuk grens gemeen hebben, niet als ze slechts met een punt aan elkaar verbonden zijn.

De vierkleurenstelling kan in de terminologie van de grafentheorie worden beschreven als een probleem van het kleuren van grafen: Van elke planaire graaf kunnen de knopen op een dusdanige wijze in vier groepen worden verdeeld, dat geen enkele zijde twee knopen van dezelfde groep verbindt. Het blijkt uit deze formulering al, dat de vierkleurenstelling niet per se met kleuren te maken heeft: in plaats van kleurmarkeringen kan men willekeurig vier andere markeringen gebruiken, zonder dat gelijke markeringen aan elkaar grenzen.

Hoewel er nergens in de wereld meer een echt vierlandenpunt is, zouden voor een dergelijk punt twee kleuren voldoende zijn.

De stelling werd in 1852 door Francis Guthrie geponeerd. Enige tijd stond ze als vermoeden open, maar in 1879 publiceerde Alfred Bray Kempe een bewijs. Daarna stond de vierkleurenstelling tien jaar bekend als bewezen, totdat Percy John Heawood in 1890 een fout vond. Het gat in het werk van Kempe kon niet gerepareerd worden; wel gebruikte Heawood dit werk om aan te tonen dat vijf kleuren voldoende waren, en hij bewees ook diverse andere aan de vierkleurenstelling verwante stellingen.

Pas in 1976 werd een nieuw bewijs gevonden, door Kenneth Appel en Wolfgang Haken. Het lukte ze het aantal gevallen van het vierkleurenprobleem van oneindig tot 1936 te reduceren en lieten vervolgens een computer al deze speciale gevallen uitrekenen. Zo leverden zij een bewijs door gevalsonderscheiding. Sommigen beschouwen dit niet als een bewijs, omdat het de computer gebruikte en zonder computer niet te controleren is. Zij beschouwen de uitkomst meer als een experimenteel resultaat dan als wiskundig bewijs.

Hoewel in cartografische handboeken het inkleuren van kaarten besproken wordt, zijn kaartenmakers, in tegenstelling tot wiskundigen, in het algemeen niet geïnteresseerd in het minimumaantal kleuren dat voor een kaart nodig is. De tak van de wiskunde die zaken als de vierkleurenstelling bestudeert, is de topologie. Daarin kan het vraagstuk van de inkleuring algemener geformuleerd worden, zodat het ook andere vormen dan het platte vlak of de bol omvat. Het aantal benodigde kleuren kan dan anders zijn.

De vierkleurenstelling geldt alleen op een oppervlak dat topologisch gelijkwaardig is aan een plat vlak of een bol. Tekent men de kaart op een ander oppervlak, dan is het aantal benodigde kleuren anders. Vormen die overeenkomen met een vlak of een bol, zijn bijvoorbeeld een cilinder of een Mariabeeldje, zolang daar maar geen gaten in zitten. Een drinkbeker zonder oor is ook topologisch gelijkwaardig, maar een beker mét oor komt overeen met de hieronder besproken torus.

Wanneer men gebruikmaakt van een torus, kan dat met maximaal zeven kleuren. In zo'n torus grenzen de vlakken niet alleen rondom, maar ook boven en onder aan elkaar. Dit wil zeggen dat de buitenste figuren over de achterkant doorlopen naar de andere figuur die aan de rand ligt.

Wanneer men een Möbiusband gaat verdelen in vlakken, en deze daarna in gaat kleuren heeft men maximaal zes kleuren nodig.

Zie de categorie Four-color theorem van Wikimedia Commons voor mediabestanden over dit onderwerp.