Brooks-tétel

A Wikipédiából, a szabad lexikonból.

[szerkesztés] Brooks tétele

Legyen G véges, összefüggő gráf, ami nem páratlan hosszú kör vagy teljes gráf. Jelölje D(G) G maximális fokszámát, χ(G) pedig kromatikus számát. Ekkor

\chi(G)\le D(G).

[szerkesztés] Megjegyzés

A kizárt esetekre az állítás nyilvánvalóan nem igaz.