Feladat: 1.16.
a) Egy gráfról tudjuk, hogy minden pont foka legalább három. Bizonyítsuk be, hogy négy színnel jól-színezhető.
b) Hogyan általánosítható a)?
Megoldás: 1.16
a) Vegyük sorra a pontokat, az elsőt színezzük tetszőlegesen. Minden soron következőt ki tudunk színezni egy olyan színnel, amilyen színűvel még nincs összekötve, hiszen összesen legfeljebb három ponttal van összekötve, s ha már mindegyiket kiszíneztük, akkor is marad még egy szín a négy közül, amelyik nem szerepel közötttük. Ezzel kiszínezzük, majd vesszük a következő pontot.
Ez az eljárás a gráfot négy színnel jól színezi.
b) Ugyanígy bizonyítható, hogy ha egy gráfban minden pont foka legfeljebb
k, akkor
k+1 színnel jól színezhető. A bizonyítást lásd az
ALG.II.2.10. feladatnál. Lásd továbbá a megoldáshoz fűzött megjegyzéseket arról, hogy mennyiben élesíthető ez az állítás.