Megoldás: 1.26
Teljes indukcióval bizonyítunk. Az állítás
n=1-re igaz, mert egy egypontú gráf és a komplementere is 1-kromatikus.
Tegyük fel, hogy
n-re már tudjuk az állítást és vegyünk egy
n+1 pontú gráfot. Válasszuk ki egy tetszőleges
x pontját. Tekintsük a
G-x gráfot és komplementerét. Ha
G-x kromatikus száma
k, akkor az indukciós feltevésünk szerint a komplementer kromatikus száma legfeljebb
n-k. Másrészt ha
x pont foka a
G-ben
<k, akkor
G-x egy
k színű jól színezése gond nélkül kiterjeszthető rá is: azt a színt kapja, amilyen színűvel nincs összekötve. Ellenkező esetben a foka legalább
k, de akkor a komplementerben a foka legfeljebb
n-k-1, s ekkor a komplementer egy
n-k színű jólszínezéséhez vehetjük ugyanígy hozzá. A komplementernek pedig van
n-k színű jólszínezése, mert kromatikus száma legfeljebb
n-k.
Ha a gráf egy csillag, akkor két színnel színezhető. A komplementere pedig egy izolált pont és egy
n-1 pontú teljes gráf, aminek
n-1 a kromatikus száma, ez összesen
n+1. Az egyenlőség tehát fennállhat.
Van általánosabb példa is. Ha veszünk egy
k pontú teljes gráfot és annak pontjait a maradó
n-k ponttal is összekötjük, akkor a kapott gráf
k+1 kromatikus, a komplementere pedig
k darab izolált pontból és egy
n-k pontú teljes gráfból áll, aminek
n-k a kromatikus száma.