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