Twierdzenie Brooksa

Twierdzenie Brooksa – w teorii grafów twierdzenie określające relację pomiędzy maksymalnym stopniem wierzchołka i liczbą chromatyczną w grafie. Nazwa twierdzenia została ustanowiona na cześć angielskiego matematyka Rowlanda Leonarda Brooksa, który opublikował jego dowód w 1941 roku.

Graf pełny jest pokolorowany wierzchołkowo przy pomocy sześciu kolorów, a maksymalny stopień wierzchołka w tym grafie wynosi pięć

Twierdzenie

Jeżeli graf G jest spójny i nieskierowany oraz nie jest grafem pełnym ani cyklem o nieparzystej długości, to liczba chromatyczna tego grafu jest nie większa niż maksymalny stopień wierzchołka Δ w tym grafie.

$\chi (G)⩽\mathrm{\Delta }(G)$

Jeżeli graf jest grafem pełnym lub cyklem o nieparzystej długości, to jego liczba chromatyczna wynosi $\chi (G)=\mathrm{\Delta }(G)+1$