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

[szerkesztés] Megjegyzés
A kizárt esetekre az állítás nyilvánvalóan nem igaz.


Based on work by