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

De stelling van Vizing.
       
In de vorige les ontdekten we dat in het algemeen geldt voor lijnkleuringen dat  χ'   Δ    en dat in het speciale geval van een bipartiete graaf geldt  χ'  = Δ .
In 1964 bewees Vadim Vizing een preciezere bewering, namelijk de volgende:
       

Voor elke enkelvoudige graaf geldt:     χ'  =  Δ    of     χ'  =  Δ + 1    

       
Daarmee vallen de grafen dus in twee klassen uiteen:  de grafen met   χ'  = Δ  (waar zoals we al zagen de bipartiete grafen bijhoren) en de grafen met   χ'  = Δ + 1.

Het bewijs dan maar?
       
We gaan het bewijs leveren met behulp van volledige inductie.
Stel dat elke graaf met n verbindingslijnen inderdaad  (Δ + 1) - lijnkleurbaar is  (onze inductie-aanname).

Neem vervolgens een graaf met  n + 1 verbindingslijnen.

Bekijk daarvan een knooppunt K0 .
 
Laten we de buren van K0 gaan nummeren:  K1, K2, K3, K4, ...  met verbindingskleuren  c1, c2, c3, c4, ... Stel dat we dat hebben gedaan tot en met een bepaalde Km met kleur cm (in de figuur hiernaast m = 4). Dan is de graad van K0 dus minstens m.

Laat nu K0Km weg. 
Dan is de resterende graaf dus 
(Δ + 1) - lijnkleurbaar, want die heeft een verbindingslijn minder (inductieaanname). De graad van de resterende graaf is minstens m - 1 dus er zijn m kleuren beschikbaar.

Stel dat kleur c0  NIET aan K0 voorkomt (zo'n kleur is er zeker, want de graad van K0 is kleiner dan
Δ en er zijn Δ + 1 kleuren voorradig). Neem bijvoorbeeld c0 = paars in het voorbeeld hiernaast (die zit zoals je ziet niet aan K0).  Dan nemen we maar aan dat die c0 WEL aan Km zit (anders kleuren we meteen K0Km in kleur c0 en zijn we klaar).

Dus is er, behalve c0, een "nieuwe"  kleur cm  die tot nu toe nog NIET aan K0 voorkomt. Neem in het voorbeeld c4 = bruin.

       
We gaan nu vanaf knooppunt Km  een zogenaamde  Kempe-keten maken, met de kleuren c0 en cm 
Dat gaat zo:  neem de verbindingslijn met kleur c0 vanaf Km naar een buurpunt

Ga vanaf dat nieuwe buurpunt via cm  naar een volgend buurpunt, dan weer via c0 verder en zo steeds om-en-om totdat het niet verder wil.

Dat geeft in ons voorbeeld een paars-bruine Kempe-keten.

Nu zijn er twee mogelijkheden voor deze Kempe-keten:  
       

       
1. K0 zit NIET aan de keten.
in dat geval kun je in de keten alle kleuren  c0 en cm + 1 wisselen. Dan is daarna K0K4 met kleur  c0  te kleuren want die zit aan beiden niet (in ons voorbeeld rechts zou je K0K4 paars kunnen maken en alle andere paars-bruine omwisselen).
In dat geval is de graaf met de extra verbindingslijn K0K4 dus ook kleurbaar!
       
2. K0 zit WEL aan de keten.  Dan moet de keten daar via kleur cm  eindigen (doorgaan via c0 kan nu niet want c0 zat immers niet aan K0).
Maar dan is er dus kennelijk een nieuw buurpunt Km + 1 van K0 te vinden met kleur cm , immers cm kwam nog niet voor bij de andere buurpunten K1, ...Km-1 en Km zelf was niet meer verbonden met K0).
       
In geval 1 hebben we meteen aangetoond dat G  kleurbaar is.
In geval 2 gaan we het hele verhaal gewoon wr toepassen, nu met de buurpunten K1, K2, ..., Km + 1
Dus laat K0Km + 1 weg, en nummer de rest K1, ..., Km  met kleuren c1, ...cm

Herhaal het hele proces hierboven.

Als dat weer een "geval 1" oplevert zijn we weer klaar.
Als dat wr een "geval 2" oplevert gaan we het nog een keer doen, nu met genummerde buren  K1, K2, ..., Km + 2
Maar omdat de graad van K0 eindig is, kunnen we niet eeuwig geval 2 krijgen.
Er moet een keertje geval 1 komen......
Dus is G   (Δ + 1) - lijnkleurbaar.
       
q.e.d.
       
Het mooie van dit bewijs is dat het meteen ook een methode levert om zo'n kleuring te maken!
       

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