El teorema de Brooks y sus aplicaciones olímpicas

Cuándo $\chi \leq \Delta$ basta: la pregunta de Brooks

La lección anterior estableció que $\chi(G) \leq \Delta(G) + 1$. Esta cota se logra con la coloración codiciosa y es ajustada para $K_n$ y para los ciclos impares. Pero en la gran mayoría de los grafos que aparecen en olimpiadas, estos dos casos excepcionales no se dan, y la cota puede mejorarse en 1.

Pregunta natural: ¿cuándo podemos garantizar $\chi(G) \leq \Delta(G)$? Esta pregunta fue respondida completamente en 1941 por R. L. Brooks. Su teorema caracteriza exactamente las dos familias donde se necesita el $\Delta + 1$, y establece que todos los demás grafos conexos admiten una coloración propia con solo $\Delta$ colores.

La mejora de 1 puede parecer pequeña, pero en problemas olímpicos puede ser la diferencia entre una solución y una respuesta incorrecta. Además, la prueba del Teorema de Brooks contiene ideas —en particular el uso combinado de inducción y argumentos de conectividad— que son herramientas de demostración estándar en olimpiadas de nivel Iberoamericano.

Enunciado y contexto del Teorema de Brooks

Teorema de Brooks (1941): Sea $G$ un grafo conexo. Entonces $\chi(G) \leq \Delta(G)$, salvo si $G$ es un grafo completo $K_n$ o un ciclo impar $C_{2k+1}$. En estos dos casos excepcionales, $\chi(G) = \Delta(G) + 1$.

En lenguaje coloquial: todo grafo conexo que no sea completo ni ciclo impar puede colorearse con a lo sumo $\Delta$ colores.

Los dos casos excepcionales: Para $K_n$, $\Delta = n-1$ y $\chi = n = \Delta + 1$ porque todos los vértices son adyacentes entre sí. Para $C_{2k+1}$, $\Delta = 2$ y $\chi = 3 = \Delta + 1$ porque el ciclo impar no es bipartito pero sí tiene grado máximo 2.

Casos especiales inmediatos de Brooks:

— Si $G$ es conexo, no completo y no ciclo impar, con $\Delta \geq 3$: $\chi(G) \leq \Delta$.

— Si $G$ es bipartito (y no es $K_2$): $\chi(G) = 2 \leq \Delta$, consistente con Brooks.

— Si $G$ es un ciclo par $C_{2k}$: $\chi = 2 \leq \Delta = 2$, consistente.

— Si $\Delta = 1$ (grafo de aristas disjuntas): $\chi = 2 = \Delta + 1$ si $G$ tiene aristas, pues $K_2$ es el único grafo con $\Delta = 1$ y es completo.

Aplicación directa: El grafo de Petersen tiene $\Delta = 3$ y no es $K_4$ ni $C_7$. Luego, por Brooks, $\chi(\text{Petersen}) \leq 3$. Combinado con la cota inferior $\chi \geq 3$ (contiene $C_5$ impar), obtenemos $\chi = 3$ sin necesidad de construir la coloración explícita.

Prueba del Teorema de Brooks por inducción en vértices

Presentamos una demostración accesible para el nivel olímpico. La idea es inducir sobre el número de vértices, utilizando la estructura de conectividad del grafo.

Caso base: Todo grafo con un único vértice satisface $\chi = 1 \leq \Delta + 1$. Para grafos muy pequeños la verificación directa es inmediata.

Reducción al caso conexo: Basta demostrarlo para grafos conexos: si $G$ tiene componentes conexas $G_1, G_2, \ldots, G_t$, entonces $\chi(G) = \max_i \chi(G_i)$ y $\Delta(G) = \max_i \Delta(G_i)$, luego Brooks para cada componente implica Brooks para $G$.

Paso inductivo — caso de punto de corte: Si $G$ tiene un punto de corte $v$ (un vértice cuya eliminación desconecta $G$), sea $C_1, C_2, \ldots, C_t$ las componentes de $G - v$ con $t \geq 2$. El subgrafo inducido $G[V(C_i) \cup \{v\}]$ es conexo con menos vértices que $G$. Por hipótesis de inducción, cada uno admite una $\Delta$-coloración (o es $K_{\Delta+1}$ / ciclo impar, que también se colorea con $\Delta$ colores en este contexto). Recoloreando consistentemente en torno a $v$ (dando a $v$ el mismo color en todas las piezas), obtenemos una $\Delta$-coloración de $G$.

**Paso inductivo — caso 2-conexo, $\Delta \geq 3$, no completo:** Sea $G$ 2-conexo (sin puntos de corte), $\Delta(G) \geq 3$, no completo, no ciclo impar. Existe un vértice $v$ tal que $G - v$ es conexo. Ordenamos los vértices de modo que $v_n = v$ sea el último. Usando la 2-conexidad y que $G$ no es completo, podemos encontrar un orden $v_1, v_2, \ldots, v_n$ tal que: (a) $v_1$ y $v_2$ no son adyacentes entre sí pero ambos son adyacentes a $v_n$, y (b) para $i \geq 3$, el vértice $v_i$ tiene al menos un vecino posterior en la lista (es decir, un vecino $v_j$ con $j > i$). El codicioso aplicado en el orden $v_1, v_2, \ldots, v_n$ satisface: al procesar $v_i$ con $i < n$, el número de vecinos ya coloreados es estrictamente menor que $d(v_i) \leq \Delta$, pues hay al menos un vecino posterior. Luego cada $v_i$ recibe un color en $\{1, \ldots, \Delta\}$. Para $v_n$: sus vecinos ya coloreados incluyen $v_1$ y $v_2$, que recibieron el mismo color (pues son iguales bajo el codicioso cuando tienen el mismo conjunto de vecinos previos, que es vacío). Luego $v_n$ tiene a lo sumo $\Delta - 1$ colores distintos en sus vecinos, y puede recibir un color libre. $\square$

Nota: La prueba completa del caso 2-conexo requiere el Teorema de Menger para construir el orden adecuado. En olimpiadas se puede usar esta prueba con la observación clave de que $v_1$ y $v_2$ reciben el mismo color.

Aplicación a horarios: cuántas franjas para $n$ exámenes

El problema de coloración de horarios es la aplicación más directa del número cromático en la vida real y en olimpiadas:

Problema: Una universidad tiene $n$ exámenes finales. Dos exámenes son "incompatibles" si hay al menos un estudiante inscrito en ambos (no puede rendir dos exámenes al mismo tiempo). ¿Cuál es el mínimo número de franjas horarias necesarias para programar todos los exámenes de modo que no haya conflictos?

Modelado: Construimos el grafo de conflictos $G$: los vértices son los $n$ exámenes y conectamos dos exámenes con una arista si son incompatibles. Una programación válida es exactamente una coloración propia de $G$: cada color representa una franja horaria, y exámenes del mismo color se dan simultáneamente sin conflictos. El mínimo número de franjas es $\chi(G)$.

Aplicación de Brooks: Si el máximo número de exámenes incompatibles con un examen dado es $\Delta$, entonces por Brooks se pueden programar todos los exámenes en $\Delta$ franjas (salvo casos degenerados). En la práctica, $\Delta + 1$ franjas siempre bastan (por el codicioso), y $\Delta$ franjas bastan a menos que el grafo de conflictos sea completo o un ciclo impar.

Ejemplo concreto: 6 exámenes con conflictos: $\{1,2\}, \{1,3\}, \{2,4\}, \{2,5\}, \{3,4\}, \{3,6\}, \{4,5\}, \{5,6\}$. El grado máximo es $\Delta = 3$ (vértices 2, 3, 4 tienen grado 3). El grafo no es $K_4$ ni $C_7$. Por Brooks, $\chi \leq 3$. Coloración: franja A: $\{1, 4, 6\}$, franja B: $\{2, 6, \ldots\}$... construcción directa: $f(1) = 1, f(2) = 2, f(3) = 2, f(4) = 3, f(5) = 1, f(6) = 3$. Verificamos: todas las aristas conectan colores distintos ✓. Se necesitan exactamente 3 franjas.

Problema olímpico: cota de Brooks en acción

Problema (Olimpiada Iberoamericana 2003, P2, adaptado): En un torneo de ajedrez con $n$ jugadores, cada par de jugadores juega exactamente una partida. Después del torneo, se quiere organizar los trofeos de modo que no haya dos jugadores del mismo "grupo de rendimiento" que se hayan enfrentado en la ronda final (la última partida que cada uno jugó). ¿Cuántos grupos mínimos son necesarios en el peor caso?

Modelado: Construimos el grafo $G$ donde los vértices son los $n$ jugadores y las aristas conectan a los jugadores que jugaron entre sí en la ronda final. Cada jugador jugó exactamente una "última partida", así que cada vértice tiene grado a lo sumo 1 en $G$ (los dos jugadores de la última partida se conectan mutuamente). El grafo $G$ es entonces un matching (colección de aristas disjuntas). El número mínimo de grupos es $\chi(G)$.

Cálculo: Un matching es bipartito (no tiene ciclos, luego no tiene ciclos impares). Por tanto $\chi(G) = 2$ si hay al menos una arista (al menos un par jugó su última partida mutuamente), y $\chi(G) = 1$ si no hay aristas (nadie tuvo última partida... lo que no ocurre). Luego se necesitan a lo sumo 2 grupos. $\square$

Problema más profundo (variante olímpica real): Un grafo $G$ es $k$-regular con $k \geq 3$ y no es $K_{k+1}$. Demuestra que $\chi(G) \leq k$. Solución: $G$ es regular con grado máximo $\Delta = k$. Como $G$ no es $K_{k+1}$ (el único grafo $(k)$-regular completo), y $G$ no es un ciclo impar si $k \geq 3$ (pues los ciclos son 2-regulares), Brooks garantiza $\chi(G) \leq \Delta = k$. $\square$

Problema tipo IbAm (nivel 3): Sea $G$ un grafo con $n$ vértices y grado máximo $\Delta$. Se remueven $m$ aristas de $G$ para obtener un grafo $H$. Demuestra que $\chi(H) \leq \Delta$. Solución: $\Delta(H) \leq \Delta(G) = \Delta$. Si $H$ no es $K_{\Delta+1}$ ni ciclo impar: por Brooks $\chi(H) \leq \Delta(H) \leq \Delta$. Si $H$ es $K_{\Delta+1}$: entonces $G$ tenía todos los vértices de $K_{\Delta+1}$ más las $m$ aristas removidas, y tenía grado máximo $\geq \Delta$, consistente. Pero $K_{\Delta+1}$ tiene $\Delta+1$ vértices de grado $\Delta$, y $\chi(K_{\Delta+1}) = \Delta + 1$... Aquí la cota no puede mejorarse sin más hipótesis sobre $m$. El enunciado correcto requiere que $m$ sea suficientemente grande para romper toda copia de $K_{\Delta+1}$.

Lección clave: El Teorema de Brooks es poderoso pero requiere verificar las dos hipótesis de exclusión (ni $K_n$ ni ciclo impar). En olimpiadas, la estrategia es: (1) calcular $\Delta$, (2) verificar que el grafo no cae en los dos casos excepcionales, (3) concluir $\chi \leq \Delta$. Esto es mucho más limpio que construir una coloración explícita.