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.

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.

${\displaystyle \chi (G)\leqslant \Delta (G)}$

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

Przypisy