door wnvl1 » wo 15 apr 2026, 22:59
Ik heb aan AI gevraagd om het bewijs even eenvoudig samen te vatten. Onderstaande tekst geeft zonder dat ik het daarom helemaal begrijp wel een goed idee van hoe het bewijs werkt. Ik kan me er zo wel wat bij voorstellen.
--------------
Het vierkleurenprobleem stelt dat elke kaart in het vlak kan ingekleurd worden met hoogstens vier kleuren, zodanig dat aangrenzende gebieden verschillende kleuren hebben. Dit probleem kan zonder verlies van algemeenheid vertaald worden naar de grafentheorie, waarbij gebieden worden voorgesteld als knopen en aangrenzende gebieden als verbindingen tussen knopen.
Eerst vereenvoudigt men het probleem door elke kaart te trianguleren, dat wil zeggen dat men extra verbindingen toevoegt zodat elk gebied begrensd wordt door precies drie zijden. Dit verandert het probleem niet, want als de uitgebreidere graaf met vier kleuren kan worden ingekleurd, dan geldt dat ook voor de oorspronkelijke graaf.
Vervolgens gebruikt men de formule van Euler, namelijk \( v - e + f = 2 \), samen met het feit dat in een getrianguleerde graaf elke zijde tot precies twee driehoeken behoort, zodat \( 2e = 3f \). Hieruit volgt dat
\[
\sum_{i}(6 - i)v_i = 12,
\]
waarbij \( v_i \) het aantal knopen van graad \( i \) voorstelt. Omdat deze som positief is, moet er minstens één knoop bestaan met graad kleiner dan of gelijk aan vijf.
Men redeneert vervolgens via tegenspraak. Stel dat er een graaf bestaat die niet met vier kleuren kan worden ingekleurd, en neem een minimale dergelijke graaf \( G \). In deze graaf kan geen knoop voorkomen met graad kleiner dan of gelijk aan drie, want dan kan men deze knoop verwijderen, de kleinere graaf inkleuren, en de knoop daarna terugplaatsen en inkleuren.
Ook knopen van graad vier kunnen uitgesloten worden met behulp van zogenaamde Kempe-ketens, waarbij men kleuren langs bepaalde paden verwisselt om een geldige inkleuring te bekomen.
Het moeilijke geval is dat van knopen met graad vijf. De oorspronkelijke redenering van Kempe voor dit geval bleek echter fout te zijn. Moderne bewijzen lossen dit op door niet slechts één knoop te beschouwen, maar grotere lokale structuren, zogenaamde configuraties.
Men toont enerzijds dat een eindige verzameling van configuraties onvermijdelijk is, wat betekent dat elke planaire graaf minstens één van deze configuraties bevat. Anderzijds toont men dat elk van deze configuraties reduceerbaar is, wat betekent dat elke geldige inkleuring van de rest van de graaf kan uitgebreid worden tot de configuratie zelf.
Om aan te tonen dat een verzameling configuraties onvermijdelijk is, gebruikt men de zogenaamde discharging-methode. Hierbij kent men aan elke knoop een beginlading toe gelijk aan \( 6 - \deg(v) \), en herverdeelt men deze lading volgens vaste regels. Omdat de totale lading positief blijft, moeten bepaalde configuraties noodzakelijk voorkomen.
Ten slotte wordt met behulp van computerondersteuning nagegaan dat alle configuraties in de onvermijdelijke verzameling effectief reduceerbaar zijn. Hieruit volgt dat een minimale tegenvoorbeeldgraaf niet kan bestaan, en dus dat elke planaire graaf met vier kleuren kan worden ingekleurd.
Ik heb aan AI gevraagd om het bewijs even eenvoudig samen te vatten. Onderstaande tekst geeft zonder dat ik het daarom helemaal begrijp wel een goed idee van hoe het bewijs werkt. Ik kan me er zo wel wat bij voorstellen.
--------------
Het vierkleurenprobleem stelt dat elke kaart in het vlak kan ingekleurd worden met hoogstens vier kleuren, zodanig dat aangrenzende gebieden verschillende kleuren hebben. Dit probleem kan zonder verlies van algemeenheid vertaald worden naar de grafentheorie, waarbij gebieden worden voorgesteld als knopen en aangrenzende gebieden als verbindingen tussen knopen.
Eerst vereenvoudigt men het probleem door elke kaart te trianguleren, dat wil zeggen dat men extra verbindingen toevoegt zodat elk gebied begrensd wordt door precies drie zijden. Dit verandert het probleem niet, want als de uitgebreidere graaf met vier kleuren kan worden ingekleurd, dan geldt dat ook voor de oorspronkelijke graaf.
Vervolgens gebruikt men de formule van Euler, namelijk \( v - e + f = 2 \), samen met het feit dat in een getrianguleerde graaf elke zijde tot precies twee driehoeken behoort, zodat \( 2e = 3f \). Hieruit volgt dat
\[
\sum_{i}(6 - i)v_i = 12,
\]
waarbij \( v_i \) het aantal knopen van graad \( i \) voorstelt. Omdat deze som positief is, moet er minstens één knoop bestaan met graad kleiner dan of gelijk aan vijf.
Men redeneert vervolgens via tegenspraak. Stel dat er een graaf bestaat die niet met vier kleuren kan worden ingekleurd, en neem een minimale dergelijke graaf \( G \). In deze graaf kan geen knoop voorkomen met graad kleiner dan of gelijk aan drie, want dan kan men deze knoop verwijderen, de kleinere graaf inkleuren, en de knoop daarna terugplaatsen en inkleuren.
Ook knopen van graad vier kunnen uitgesloten worden met behulp van zogenaamde Kempe-ketens, waarbij men kleuren langs bepaalde paden verwisselt om een geldige inkleuring te bekomen.
Het moeilijke geval is dat van knopen met graad vijf. De oorspronkelijke redenering van Kempe voor dit geval bleek echter fout te zijn. Moderne bewijzen lossen dit op door niet slechts één knoop te beschouwen, maar grotere lokale structuren, zogenaamde configuraties.
Men toont enerzijds dat een eindige verzameling van configuraties onvermijdelijk is, wat betekent dat elke planaire graaf minstens één van deze configuraties bevat. Anderzijds toont men dat elk van deze configuraties reduceerbaar is, wat betekent dat elke geldige inkleuring van de rest van de graaf kan uitgebreid worden tot de configuratie zelf.
Om aan te tonen dat een verzameling configuraties onvermijdelijk is, gebruikt men de zogenaamde discharging-methode. Hierbij kent men aan elke knoop een beginlading toe gelijk aan \( 6 - \deg(v) \), en herverdeelt men deze lading volgens vaste regels. Omdat de totale lading positief blijft, moeten bepaalde configuraties noodzakelijk voorkomen.
Ten slotte wordt met behulp van computerondersteuning nagegaan dat alle configuraties in de onvermijdelijke verzameling effectief reduceerbaar zijn. Hieruit volgt dat een minimale tegenvoorbeeldgraaf niet kan bestaan, en dus dat elke planaire graaf met vier kleuren kan worden ingekleurd.
