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.
left|thumb|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.
Jeżeli graf jest grafem pełnym lub cyklem o nieparzystej długości, to jego liczba chromatyczna wynosi
Przypisy
Brooksa