Woord - Domino
Je hebt de 10 kaartjes hiernaast en moet die in een cirkel leggen zodat elk kaartje een letter gemeenschappelijk heeft met zijn beide buren. Kan dat?

Laten we een graaf tekenen van de relatie "Heeft een letter gemeenschappelijk met".
Die ziet er uit als hieronder.
Er bestaat een oplossing als je in deze graaf een zogenaamd Hamilton-circuit kunt vinden: een route die alle woorden precies één keer langsgaat en begint en eindigt bij hetzelfde woord.
Is zo'n circuit er?

NEE!

Waarom niet?

Dat kun je zó zien:
Stel dat er zo'n Hamilton-circuit is. Kleur de verbindingen van dat circuit dan om-en-om groen en blauw.
Kleur verder de niet-gebruikte verbindingen rood
Dan is de hele graaf gekleurd en komen er bij elk woord drie verschillend gekleurde lijnen aan.

Is de graaf met drie keuren zo te kleuren dat dat klopt?

 
De vijf buitenste lijnen moeten twee gelijke kleuren hebben (pigeon-hole)
Stel dat dat de lijnen tussen  MUF-MET en VLOT-GIL zijn (de figuur is symmetrisch, dus met twee anderen gaat het bewijs precies zo) en stel dat die lijnen groen zijn.
MET-VLOT heeft dus een andere kleur. Stel blauw.
MET-WERP en VLOT-DOS liggen dan vast: rood
Omdat GAF - MUF en GAF - GIL beiden niet groen kunnen zijn, moet GAF-BARS dat wel zijn.
Maar nu moeten BAS-WERP en BAS-DOS beide verschillend van groen en van elkaar zijn gekleurd. Dat kan alleen als één van beiden rood is, en dat mag niet want WERP en DOS zijn al met rood verbonden.

Kortom:deze graaf is niet te kleuren.
In het hele verhaal hierboven zijn de kleuren en hun functie willekeurig. Het gaat er alleen om of de graaf met drie kleuren is te kleuren.