Ha $G$ nem teljes gráf, vagy páratlan csúcsú kör, akkor
\( \chi(G) \leq \Delta(G) \)
A Brooks-tétel egy felső becslés a kromatikus számra.
1.
a) Mekkora a kromatikus száma ennek a gráfnak?
b) Mekkora a kromatikus száma ennek a gráfnak?
c) Mekkora a kromatikus száma ennek a gráfnak?
d) Egy $G$ gráfban 1000 darab csúcstól eltekintve minden pont foka legfeljebb 999. Bizonyítsuk be, hogy a gráf kromatikus száma legfeljebb 1000.
e) Egy $G$ gráf csúcshalmaza legyen a $V(G)=\{1,2,3,\dots,30\}$ és két csúcs akkor legyen szomszédos, ha a különbségük legalább 6. Mekkora ennek a gráfnak a kromatikus száma?
