Ha egy gráf maximális fokszáma 5, akkor a gráf kromatikus száma 6, tehát a csúcsait minimálisan hatféle különböző színnel lehet kiszínezni úgy, hogy a szomszédos csúcsok más-más színt kapjanak?

Nem.

Legyen a gráf csúcsainak halmaza V = {A, B, C, D, E, F}

Az élek halmaza pedig E = {{F,A}, {F,B}, {F,C}, {F,D}, {F,E}}.

Ekkor a (V, E) gráf A, B, C, D és E csúcsainak fokszáma 1, az F csúcsé 5, tehát a maximális fokszám 5, ahogy a feltételedben szerepel.

Viszont az egy jó színezés, hogy az A, B, C, D és E csúcsokat karmazsinnal festjük be (mert nincs köztük él), az F csúcsot pedig okkersárgára színezzük. Ezzel minden csúcsot befestettünk, és csak két színt használtunk, tehát a 2 szín is elég volt, nem kellett 6.

[link]