Otra Demostración del Teorema de Brookes | Julian a través del lente

Un resultado clásico de la teoría de grafos establece que dado $G$ un grafo no dirigido:

χ (G) \leq Δ (G) + 1

Donde $χ (G)$ es el número mínimo de colores necesarios para pintar los nodos de $G$ con la restricción habitual de que ningún nodo tenga el mismo color que alguno de sus vecinos, y $Δ (G) = ma x_{v \in V (G)} (d g (v))$ , es decir, el grado máximo. Este resultado se conoce como el Teorema de Brookes.

La forma usual de demostrar este resultado es utilizar el algoritmo de coloreo voraz: se recorre cada nodo y se elige el color más bajo que aún no haya sido usado por ninguno de sus vecinos. Es bastante directo probar el resultado con esta idea: cada nodo tiene a lo sumo $Δ (G)$ vecinos, por lo que el color más alto que se podría elegir es $Δ (G) + 1$ . Este es el resultado que probablemente encontrarás en la mayoría de los libros y cursos de teoría de grafos. El otro día estaba hablando con unos amigos cuando surgió este tema y se nos ocurrió esta demostración.

Para mayor completitud, incluyo aquí algunas definiciones:

Definición: La vecindad de un nodo $v \in V (G)$ es

N (v) = {w \in V (G) : (v, w) \in E (G)}

Definición: La vecindad cerrada de un nodo $v \in V (G)$ es

N [v] = N (v) \cup {v}

Concretamente, la idea reside en la siguiente observación: dada una coloración minimal $f : V (G) \to [χ (G)]$ , $\exists v \in V (G) : # f (N [v]) = χ (G)$ . ¿Qué significa esto? Significa que existe un vértice tal que el número de colores en la vecindad cerrada de $v$ es exactamente $χ (G)$ . Asumiendo que el enunciado anterior es verdadero, notemos que $# N [v] = d g (v) + 1$ , luego:

χ (G) = # f (N [v]) \leq d g (v) + 1 \leq Δ (G) + 1

Que es precisamente el Teorema de Brookes. Entonces, si encontramos una forma de demostrar que $\exists v \in V (G) : # f (N [v]) = χ (G)$ , habremos terminado. Planteemos el enunciado formal:

Lema: Dado $G$ un grafo no dirigido, $f$ una coloración minimal de $G$ , $\exists v \in V (G) : # f (N [v]) = χ (G)$ .

Demostración: Supongamos que $\forall v \in V (G) : # f (N [v]) \neq = χ (G)$ . Claramente, $# f (N [v])$ no puede ser mayor que $χ (G)$ , pues tal situación contradiría que $f$ es una coloración minimal de $G$ . Por lo tanto, tenemos que toda vecindad cerrada de $G$ tiene $# f (N [V]) < χ (G)$ . Sea $C_{k} = {v \in V (G) : f (v) = k}$ , donde $k \in [χ (G)]$ ; estos $C_{k}$ son los nodos coloreados con el color $k$ . Solo por brevedad, llamemos $C = C_{χ (G)}$ a los nodos coloreados con el último color.

Dado cualquier nodo $w \in C$ , podemos cambiar su color por otro color más bajo que no esté usado en su vecindad, porque $# f (N [w]) < χ (G)$ (esto significa que no todos los colores están usados en la vecindad, por lo que al menos podemos tomar $χ (G) - 1$ ). Llamemos $c_{w}$ a ese color más bajo que elegimos. Notemos que por construcción no hay conflictos con ningún vecino.

Definamos $g : V \to [χ (G) - 1]$ como

g (v) = {c_{v} f (v) v \in C otherwise

Veamos que esto es una coloración: dado cualquier $e = (v, w) \in E (G)$ , queremos verificar que $g (v) \neq = g (w)$ . Supongamos que $g (v) = g (w)$ ; entonces hay tres casos posibles:

$v \in C \land w \in C$ : $C$ era el conjunto de nodos coloreados con $χ (G)$ según $f$ , que era una coloración por hipótesis. Por lo tanto, esto no puede ocurrir, ya que contradiría que $f$ es una coloración propia.
$v \neq \in C \land w \neq \in C$ : tenemos que $g (v) = f (v) \land g (w) = f (w)$ , luego $f (v) = f (w)$ , lo que contradiría la hipótesis de que $f$ es una coloración propia.
$v \in C \land w \neq \in C$ : por definición, tenemos que $w \in N [v]$ , y elegimos $g (v)$ de modo que no entre en conflicto con ninguno de sus vecinos. Por lo tanto, esto tampoco puede ocurrir.

Finalmente, ¡hemos demostrado que $g$ es una coloración! Sin embargo, esto significa que construimos una coloración de $G$ que usa menos colores que $χ (G)$ . Esto es un absurdo, y por lo tanto $f$ no puede haber sido una coloración minimal.

Relacionados