Egy 8x8-as sakktáblára feltettünk 40 lovat úgy, hogy minden sorban és minden oszlopban pontosan 5 legyen. Mutassuk meg, hogy a lovakat ki lehet színezni 5 színnel úgy, hogy minden sorban és minden oszlopban 5 különböző színű ló legyen?

A színeket jelölje 1-2-3-4-5 számok. Ekkor a

1 2 3 4 5

5 1 2 3 4

4 5 1 2 3

3 4 5 1 2

2 3 4 5 1

tökéletes színezés.

segítség: csinálj egy olyan segédgráfot, aminek két csúcsosztálya van (tehát páros) 8-8 csúccsal, az egyik osztály csúcsai feleljenek meg a sakktábla sorainak (tehát az egyik csúcs az első sornak, egy másik a másodiknak, .., a nyolcadik csúcs a nyolcadik sornak), a másik osztály 8 csúcsa meg az oszlopoknak.

Két különböző osztályban lévő csúcs közé akkor húzzál be élt, ha a nekik megfelelő sor és oszlop metszetében áll egy ló.

Ezen a segédgráfon könnyen megfogalmazható a feladat feltétele és a bizonyítandó állítás is, és könnyen is bizonyítható.