Feladat: 1.24.
a) Egy
3n pontú gráfról tudjuk, hogy három színnel jólszínezhető. Bizonyítsuk be, hogy a komplementere jólszínezéséhez legalább
n színre van szükség.
b) Egy
jn pontú gráfról tudjuk, hogy
j színnel jólszínezhető. Bizonyítsuk be, hogy a komplementere jólszínezéséhez legalább
n színre van szükség.
Megoldás: 1.24
a) A három színnel jól színezhetőség azt jelenti, hogy három osztályba sorolhatók a gráf úgy, hogy azonos csoportbeli pontok között ne fusson él. Ha
3n pont van, akkor az egyik csoport legalább
n pontból áll, s ezek között minden él a komplementerben fut. Tehát a komplementerben minden pontnak más színűnek kell lennie.
b) Az a)-ban adott gondolatmenet szó szerint elismételhető.