Mennyi G gráf kromatikus száma, ha G csúcshalmaza (1,2,3, . ,100) és ij pontosan akkor él, ha i nem egyenlő j, illetve i és j nem relatív prímek?

Ha megnézzük, akkor bizonyos számok csoportot alkotnak:

2-4-6-8-...-100

3-6-9-12-...-99

5-10-15-...-100

7-14-21-...-98

.

.

.

Mindegyik prímszámmal végigjátsszuk ezt, és kapunk egy-egy sorozatot; ezek a számhalmazok teljes részgráfot alkotnak a gráfon belül; természetesen a csoportok között vannak átkötések (pl. a 30 a 2-es, 3-as és 5-ös csoportban is benne van), de mi azt fogjuk belátni, hogy 50 színnel ki lehet színezni ezt a gráfot; a legnagyobb részgráf az első csoport (ami a 2-essel kezdődik), ebben összesen 50 tag van, tehát egy K(50)-et találtunk. Ennek a gráfnak (milyen meglepő) 50 színnel tudjuk csak kiszínezni a csúcsait. Az ehhez kapcsolódó "külső" pontok sok vizet nem zavarnak, mivel csak akkor lennének érdekesek, ha az összes ponthoz össze lennének kötve, így K(50+) lenne, de nem így van. Tehát a felhasznált 50 szín a gráf többi részéhez is elég lesz (az izolált pontok pedig az 1, valamint az 50-nél nagyobb prímszámokhoz is elég az 50 szín bármelyike).

Tehát a gráf kromatikus száma 50.