En teoría de grafos, el teorema de Brooks establece la relación entre la valencia máxima del grafo con el número cromático: Si G es un grafo conexo que no sea completo ni un ciclo de longitud impar, entonces
Basta buscar una ordenación adecuada y aplicar el algoritmo voraz para colorear secuencialmente.
El vértice x lo colocamos en el último lugar de la ordenación, es decir, x=vn .
Los vértices adyacentes a x los enumeramos vn-s, vn-s-1, ..., vn-1, luego consideramos los adyacentes a vn-1 que no han sido ordenados, luego los de vn-2, y así hasta ordenarlos todos (lo cual es posible al ser G conexo).
Luego, en cada paso del algoritmo hay a lo sumo Δ-1 colores prohibidos.