Teorema de Brooks

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:

En donde ${\displaystyle \Delta }$ es la valencia máxima del grafo G.

La siguiente demostración es sólo para grafos no regulares. Basta buscar una ordenación adecuada y aplicar el algoritmo voraz para colorear secuencialmente.

Sea G un grafo de n vértices y x un vértice tal que ${\displaystyle g(x)=s<\Delta \,}$ (que existe por la no regularidad). El vértice x lo colocamos en el último lugar de la ordenación, es decir, x=v_n . Los vértices adyacentes a x los enumeramos v_n-s, v_n-s-1, ..., v_n-1, luego consideramos los adyacentes a v_n-1 que no han sido ordenados, luego los de v_n-2, y así hasta ordenarlos todos (lo cual es posible al ser G conexo).

En esta ordenación {v₁, v₂, ..., v_n}, todos los vértices tienen un vértice (o más) adyacente posterior (con subíndice mayor) excepto el vértice x . Luego, el número de vértices adyacentes con subíndice menor es igual o menor a Δ .

Al aplicar el algoritmo voraz para colorear surgen los colores prohibidos. El número de colores prohibidos en el paso k de la ejecución del algoritmo es el número de colores usados por lo vértices adyacentes anteriores, y por los vértices anteriores. Luego, en cada paso del algoritmo hay a lo sumo Δ-1 colores prohibidos. Por lo tanto, se puede colorear G con Δ colores.

• Brooks, R. L. (1941), "On colouring the nodes of a network", Proc. Cambridge Philosophical Society, Math. Phys. Sci. 37: 194–197