Feladat: 1.25.
* Bizonyítsuk be, hogy ha
G egy
n pontú egyszerű gráf, akkor
G kromatikus számának és a komplementere kromatikus számának az összege legalább
2n.
Fennállhat-e egyenlőség?
Megoldás: 1.25
* Ha az
n pontú gráf kromatikus száma
k, akkor az előző (=
1.24.) feladat a) és b) gondolatmenete szerint van egy legalább
⌈n/k⌉ pontból álló független ponthalmaz. Ennek pontjai között minden él a komplementerben fut, tehát a komplementer kromatikus száma legalább ennyi. A kettő összege tehát legalább
(Használtuk a számtani és mértani közép közötti összefüggést.)
Egyenlőség nyilván csak akkor állhat, ha
n=
m2
négyzetszám. Ezesetben a gráf pontjait osszuk
m darab
m-es csoportra és kössük össze a különböző csoportokhoz tartozó pontokat. Az így kapott gráf kromatikus száma éppen
m. Másrészt komplementere
m darab páronként pontdiszjunkt
m pontú teljes gráfokból áll, ezek kromatikus száma is
m. Tehát mind a gráfnak, mind a komplementerének a kromatikus száma
n, azaz e gráfra fennáll az egyenlőség.