1: Het vierkleurenprobleem 2: Wat is een kaart? 3: De telformule 4: De methode van het reduceren 5: Het 'bewijs' van Kempe 6: Ontladen 7: De hulp van de computer
In de eerste helft van de twintigste eeuw gingen de onderzoeken verder op het spoor van een onvermijdelijke set van reduceerbare configuraties. De Duitser Heinrich Heesch (1906-1995) speelde in dit onderzoek een centrale rol. Van hem stamt de techniek van het 'ontladen' waarmee nieuwe onvermijdelijke sets opgespoord kunnen worden, zoals de onvermijdelijke set {tweehoek, driehoek, vierhoek, twee vijfhoeken aan elkaar, een vijf- en zeshoek aan elkaar}, zie figuur 6.

Figuur 6 Onvermijdelijke set {tweehoek, driehoek, vierhoek, twee vijfhoeken aan elkaar, een vijf- en zeshoek aan elkaar}
We laten zien hoe je met ontladen kunt bewijzen dat elke kaart inderdaad ten minste één van deze configuraties moet bevatten.
Ken aan elk land de 'lading' 6 - k (k is het aantal grenzen) toe. Vijfhoeken hebben dus lading 1, zeshoeken lading 0, zevenhoeken -1, achthoeken -2, enzovoorts.
Stel nu (tegen beter weten in) dat geen van de configuraties uit figuur 6 in de kaart voorkomt. Bereken de totale lading van de hele kaart. Omdat er geen twee-, drie- of vierhoeken in voorkomen, geldt: c2 = c3 = c4 = 0. De totale lading van de kaart is dan: 1 × c5 + (-1) × c7 + (-2) × c8 + (-3) × c9- .... Volgens de telformule levert dit: c5 - c7 - 2c8 - 3c9 - ... = 12; de totale lading is dus 12.
Verdeel nu (ontladen) de lading 1 van elke vijfhoek netjes (5 keer 1/5) over zijn 5 buren. Merk op dat rond elke vijfhoek alleen zevenhoeken of hoger zitten (onze aanname) met ladingen -1, -2 enzovoorts. De lading van elke vijfhoek wordt dus 0, die van elke zeshoek blijft 0 en die van elke zevenhoek of hoger worden
-4/5, -9/5, enzovoorts. De totale lading van de landkaart is dan dus negatief. Maar de totale lading is 12 en positief. We stuiten op een tegenspraak, en concluderen dat er geen kaart kan bestaan waarin niet ten minste één van de vijf configuraties voorkomt.
prev | 1 | 2 | 3 | 4 | 5 | 6 | 7 | next
|