Teorema de Brooks
# 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:

* Si G es un grafo conexo que no sea completo ni un ciclo de longitud impar, entonces $\chi (G)\leq \Delta \,$
* R. L. Brooks, (1941)

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

## Demostración básica

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 $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_1,$ $v_2,$ ..., $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.

