vier kleuren

© h.hofstede (h.hofstede@hogeland.nl)

Het vierkleurenprobleem.

We zagen al eerder dat elke planaire graaf kleurbaar is met 6 kleuren. (tenminste als je opgave 2 van deze les hebt gemaakt).

Kan het ook met 5 kleuren?

Ja.

Bewijs:
Stel dat het niet met 5 kleuren kan. Kies de kleinst mogelijke graaf die niet met 5 kleuren te kleuren is.

Die graaf heeft minstens één knooppunt met graad ≤ 5 (stelling dat δ ≤ 5 uit deze les)
Laat dat knooppunt weg uit de graaf, dan is de overblijvende graaf dus met 5 kleuren WEL kleurbaar (onze graaf was immers de kleinste niet-kleurbare)

Kleur die overblijvende graaf.

Omdat G niet met vijf kleuren kleurbaar is moet het weggelaten knooppunt dus grenzen aan alle vijf de gebruikte kleuren (anders kun je het na kleuren gewoon weer toevoegen en er een kleur voor kiezen)

Bekijk nu de graaf die je krijgt door alleen maar alle rode en groene punten van G te nemen. Dan moet daarin een pad van rood naar groen bestaan. Als dat er niet is, zou je alle punten die met dat bovenste rode punt zijn verbonden van kleur kunnen wisselen (groen wordt rood en rood wordt groen) en dan heeft ons weggelaten punt nog maar vier buurkleuren en is het weer toe te voegen met de vijfde kleur.

Je ziet hiernaast nu een cykel rood-midden-groen-rood. Dat is een Jordankromme. Blauw ligt in het binnengebied daarvan en geel in het buitengebied.

Omdat blauw-geel ook verbonden zijn (zelfde redenering als rood-groen), moet het blauw-gele pad de rood-groene cykel ergens snijden in een knooppunt (het moet wel in een knooppunt zijn want G is planair)
Maar een rood-groen knooppunt kan niet blauw-geel zijn!
■

Kan het ook met 4 kleuren?

Dat is jarenlang een grote vraag geweest. Voor uitgebreide uitleg daarover en de geschiedenis daarvan moet je hier maar kijken. Ik wil me de rest van deze les vooral richten op wat grafen-theoretische kanten van dit probleem.
De volgende drie beweringen zijn gelijk (let wel: ik zeg dus niet dat de beweringen WAAR zijn, maar dat ze GELIJKWAARDIG zijn!):

1.	Elke planaire graaf is 4-punt-kleurbaar.
2.	Elke vlakke graaf is 4-vlak-kleurbaar.
3.	Elke enkelvoudige 2-lijnverbonden 3-reguliere planaire graaf is 3-lijn-kleurbaar.

Grappig toch? Daar staan drie beweringen over het kleuren van punten, van facetten en van lijnen. De tweede is de vorm waarin je meestal leest over het vierkleurenprobleem.

Bewijs.

(2) volgt direct uit (1) door van graaf G de duale graaf te G* bekijken, immers dan gaan facetten over in knooppunten.

(3) volgt uit (2) via een leuk trucje. Stel dat je de facetten van G hebt gekleurd met 4 kleuren,
Noem dan ROOD = (0, 0), GROEN = (1, 0), PAARS = (0, 1) en BLAUW = (1,1). De lijnen van G krijgen dan een kleur door de vectoren van de aangrenzende facetten bij elkaar op te tellen (modulo 2).
Dan geeft dat een correcte 3-kleuring van de lijnen! Ga zelf maar na dat dat altijd klopt!

(Je kunt bijvoorbeeld zien dat nooit een verbindingslijn rood wordt: het wordt altijd groen, paars of blauw, dus 3-kleuren. Verder kun je ook makkelijk zien dat drie lijnen bij één knooppunt altijd verschillende kleuren hebben)

Voorbeeld:

(1) volgt uit (3)
Neem een triangulatie T in het platte vlak (dat is een graaf met allemaal driehoeken, dus waarvan elk facet graad 3 heeft, de buitenste telt niet mee)
Dan is de duale graaf T* daarvan dus een 2-lijnverbonden 3-reguliere graaf .
(immers de graad van een facet van T wordt bij de duale graaf de graad van het nieuwe knooppunt van T*, en omdat elk facet van T aan 3 anderen grenst krijgt elk knooppunt van T* drie verbindingslijnen; zie de les over duale grafen).

Maar volgens (3) zijn die lijnen van T* dan 3-lijn-kleurbaar.
Dit is er aan de hand:

Ik zal laten zien dat daaruit volgt dat de graaf T* dan 4-vlak-kleurbaar is. Dat gaat zó:

Kies twee van de drie kleuren van T* bijvoorbeeld rood en blauw, en laat alle lijnen van groen gewoon weg.
Dat geeft een deelgraaf T₁₂*. Maar die graaf bestaat nog steeds uit alle knooppunten van T*, immers alle knooppunten hebben alle drie de kleuren.
Dat betekent dus dat alle knooppunten van T₁₂* precies twee verbindingslijnen hebben (van elke kleur één) dus T₁₂^* bestaat uit een serie losse cykels! En hetzelfde geldt natuurlijk als je bijvoorbeeld rood weglaat (geeft T₂₃^*). Kijk maar:

Losse cykels zijn 2-vlak-kleurbaar.
Laten we de facetten van de twee grafen T₁₂^* en T₂₃^* elk met twee kleuren kleuren, bijvoorbeeld geel-paars voor T₁₂^* en oranje-bruin voor T₂₃^*
Leg ze dan weer over elkaar..... Dan krijg je T* weer.
Dan is elk facet van de totale graaf T^*de doorsnede van eentje van T₁₂^* en eentje van T₂₃^*. Dus kun je elk facet één van de nieuwe "kleuren" geel-oranje, geel-bruin, paars-oranje en paars-bruin geven, dus T^* is 4-vlak kleurbaar.

Maar als T* 4-vlak-kleurbaar is, dan is zijn duale graaf T dus weer 4-punt-kleurbaar!
Maar omdat elke planaire graaf G gezien kan worden als deel van één of andere triangulatie T (voeg er gewoon extra lijnen aan toe om overal driehoeken van te maken), is die graaf G dus óók 4-punt-kleurbaar. Daaruit volgt (1).

■