Megoldás: 1.20
Tegyük fel, hogy a gráf jól színezhető három színnel. Legyen a
z pont színe 3-as. Az
yi
pontok ebben a színezésben csak az 1 és a 2 színeket kaphatják. Viszont az
xi
pontok egy
C5
-öt alkotnak, tehát a színezésük az
1.19. feladat a) része szerint valamelyik ponttól indulva az 1,2,3,1,2. Ha a 3-as színt az
xi
pont kapta, akkor a neki megfelelő
yi
pont színe sem lehet sem 1-es, sem 2-es, mert
xi
-nek, s így
yi
-nek mindkét színű szomszédja van.
Ezzel bebizonyítottuk, hogy a feladat gráfjának kromatikus száma legalább négy. Másrészt négy színnel nyilvánvalóan jól is színezhető: az
xi
pontokat jól színezzük három színnel, az
yi
pont ugyanazt a színt kapja, mint a neki megfelelő
xi
pont, s végül
z színe a negyedik szín lesz.