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

       
1. In een graaf met als facetten alleen maar driehoeken heeft elk facet precies graad 3.
De som van alle graden is dus 3f
De som van alle graden is ook 2V
3f = 2V invullen in de regel van Euler:
f + K = V + 2   
2/3V + K = V + 2
2V + 3K = 3V + 6
V = 3K - 6
       
2. Stel dat een planaire graaf niet  6-kleurbaar is.  Kies de kleinst mogelijke graaf waarvoor dat geldt.
Die heeft in iedere geval een knooppunt met graad ≤ 5  (immers  δ ≤ 5)
Laat dat knooppunt weg, dan heb je een kleinere graaf gekregen.
Die is dus WEL 6-kleurbaar
Kleur die graaf.
Voeg nu het weggelaten knooppunt weer toe.
Omdat dat hoogstens 5 buren heeft is het altijd met één van de 6 kleuren te kleuren.
Een tegenspraak!
■
       

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