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  T12*.  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 T12* precies twee verbindingslijnen hebben  (van elke kleur n) dus T12*  bestaat uit een serie losse cykels!  En hetzelfde geldt natuurlijk als je bijvoorbeeld rood weglaat (geeft  T23*).  Kijk maar:
       
 

       
  Losse cykels zijn 2-vlak-kleurbaar.
Laten we de facetten van de twee grafen T12* en T23* elk met twee kleuren kleuren, bijvoorbeeld  geel-paars voor  T12*  en  oranje-bruin voor T23*
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 T12* en eentje van T23*.  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).
     
       

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