Zes kleuren voor een onvoorstelbaar aantal cirkels

Teken op een blad papier een stel cirkels in verschillende kleuren. De cirkels hoeven niet even groot te zijn en ze mogen elkaar overlappen. Er zijn twee voorwaarden. Eén: niet meer dan twee cirkels mogen elkaar in hetzelfde punt raken. Twee: twee cirkels die elkaar wél in hetzelfde punt raken, moeten verschillende kleuren hebben. Vraag: heb je altijd aan vijf kleuren genoeg, ongeacht het aantal cirkels?

Deze vraag werd in 1959 opgeworpen door de Duitser Gerhard Ringel, een wiskundige (en fervent surfer en vlinderverzamelaar) die faam verwierf met de zogeheten grafentheorie. Voor de duidelijkheid: snijdende cirkels hoeven níét verschillend gekleurd te worden. In een artikel uit 1984 gaf Ringel twee configuraties van cirkels waarbij vijf kleuren vereist zijn: de ene bevat acht cirkels, de andere (hier afgebeeld) negen. Het lukt niet de cirkels onder de gestelde voorwaarden met slechts vier kleuren te kleuren. Voor elke configuratie die uit maximaal zeven cirkels bestaat, zijn hooguit vier kleuren wel voldoende.

Hoeveel moeite Ringel heeft gedaan een configuratie te vinden waarvoor zes kleuren nodig zijn, vertellen de boeken niet, maar zeker is dat hij er nooit één heeft gevonden. Vandaar zijn vraag of vijf kleuren altijd volstaan.

Die vraag is nu beantwoord door vijf wiskundigen van universiteiten in Canada, Israël, Duitsland en Polen. Nee, is het antwoord. Het knappe van hun resultaat is dat ze niet één enkel voorbeeld geven van een cirkelconfiguratie waarbij zes kleuren nodig zijn, maar een algemeen bewijs leveren van het feit dat er helemaal geen grens zit aan het aantal benodigde kleuren. Het is dus mogelijk om een reeks cirkels te tekenen waarvoor zelfs duizend kleuren niet volstaan.

In theorie dan, want het aantal benodigde cirkels is groot. Héél groot. Zelfs een tekening waarvoor zes kleuren nodig zijn, is praktisch niet uit te voeren. In een e-mail schrijft Linda Kleist: „Al voor zes kleuren is het aantal cirkels in onze constructie (waarschijnlijk) groter dan het aantal atomen in het heelal.” Geen wonder dus dat niemand ooit met trial and error zo’n configuratie had gevonden.

Hoe ging het vijftal dan te werk, als je zo’n configuratie niet werkelijk op papier kunt zetten? „Ons bewijs is inductief”, zegt Kleist. „Onze methode laat zien dat als je een configuratie A hebt die niet met vier kleuren kan worden gekleurd, je een nieuwe, veel grotere configuratie B kunt construeren die niet met vijf kleuren kan worden gekleurd. Vervolgens kun je B gebruiken om, volgens hetzelfde principe, een configuratie C te maken waarvoor zes kleuren niet volstaan.” Zo kun je eindeloos doorgaan. Steeds weer kun je een nieuwe, grotere configuratie van cirkels vinden waarvoor een extra kleur nodig is. Kleist: „Bij dit inductiebewijs maken we gebruik van een oude stelling van de Hongaarse wiskundige Tibor Gallai, die we nog moesten aanpassen om hem geschikt te maken voor ons doel.”

Geen computer

Ringels cirkelprobleem doet denken aan het beroemde vierkleurenprobleem, dat erom gaat een landkaart zodanig in te kleuren dat geen twee aan elkaar grenzende landen dezelfde kleur hebben. Als aan het probleem van Ringel de extra eis wordt toegevoegd dat cirkels elkaar niet mogen overlappen, komt het exact neer op het vierkleurenprobleem. In 1976 werd bewezen dat vier kleuren áltijd volstaan. Het is daarom verrassend dat zonder de overlaprestrictie het aantal benodigde kleuren níét begrensd is.

Voor het bewijs van het vierkleurenprobleem was de hulp van een computer onontbeerlijk. Maar het bewijs van de vijf wiskundigen steekt heel anders in elkaar. Ze geven een zuiver logische redenering, zonder dat er duizenden gevallen doorgerekend hoeven te worden. De computer was louter nodig om met elkaar te kunnen communiceren. Het vijftal werkte aan het probleem sinds ze elkaar in september van vorig jaar ontmoetten, tijdens een online workshop. Kleist: „We hadden lange zoomvergaderingen en ook na de workshop hielden we contact via het beeldscherm. De meesten van ons hebben de anderen nooit persoonlijk ontmoet.”

Waar het resultaat goed voor is? „Deze vraag kun je stellen over veel wiskundige problemen die jaren open staan”, zegt Kleist. „Soms zijn de gebruikte bewijsmethoden belangrijker dan het bewijs zelf. We hopen dat dit ook met ons bewijs het geval is. De tijd zal het leren.”