El principio de extremo: el vértice más especial

La idea central: elegir lo "más especial"

El principio de extremo (o principio del caso extremo) es una de las técnicas más versátiles en combinatoria olímpica. Su formulación es simple: cuando necesites demostrar la existencia de un objeto con cierta propiedad, no busques un objeto arbitrario — elige el más extremo disponible según alguna medida natural (el más grande, el más largo, el de mayor peso, el más alejado) y demuestra que ese objeto extremal tiene la propiedad deseada.

La potencia de la técnica está en que el objeto extremal no puede ser "mejorado". Esta imposibilidad de mejora fuerza restricciones sobre su estructura: sus vecinos deben tener propiedades específicas, sus aristas adyacentes deben satisfacer condiciones especiales, y su posición en el grafo queda fuertemente constrained.

El principio de extremo es transversal: aparece en teoría de grafos (camino más largo, vértice de mayor grado), en geometría combinatoria (punto más alejado, par de puntos más distante), en teoría de números (el menor contraejemplo en demostraciones por descenso infinito), y en álgebra combinatoria (el polinomio de menor grado). En esta lección nos enfocamos en sus aplicaciones a grafos y a combinatoria geométrica.

Tres recuerdos del Capítulo 1 que son instancias del principio de extremo: (1) el camino más largo en un grafo con $\delta \geq k$ tiene longitud $\geq k$, (2) el equipo con más victorias en un torneo domina a todos, (3) el vértice de menor grado en la inducción del Teorema de los Cinco Colores. En todos estos casos, "lo más extremo" fue la clave.

Principio de extremo en grafos: caminos y ciclos

Teorema 1 (Camino más largo y vértices terminales): En todo grafo finito $G$, si $P = v_0, v_1, \ldots, v_\ell$ es un camino de longitud máxima (el más largo de todos los caminos en $G$), entonces todos los vecinos de $v_0$ y de $v_\ell$ están en $V(P)$.

Demostración: Sea $P$ el camino más largo. Supongamos que $v_0$ tiene un vecino $w \notin V(P)$. Entonces $w, v_0, v_1, \ldots, v_\ell$ es un camino de longitud $\ell + 1$, contradiciendo la maximalidad de $P$. $\square$ El argumento para $v_\ell$ es análogo.

Corolario: En un grafo con grado mínimo $\delta(G) \geq k$, el camino más largo tiene longitud $\geq k$. Prueba: en el camino más largo $P$, el vértice $v_\ell$ tiene $d(v_\ell) \geq k$ vecinos, todos en $V(P)$. El vecino $v_i$ de $v_\ell$ en $V(P)$ con menor índice satisface $i \geq 0$, luego $\ell \geq k$ (necesitamos al menos $k$ vértices intermedios en $P$ para alojar los $k$ vecinos de $v_\ell$).

Teorema 2 (Ciclo más largo en grafo 2-conexo): En un grafo 2-conexo $G$ con grado mínimo $\delta \geq k$, existe un ciclo de longitud $\geq \min(n, 2k)$, donde $n = |V(G)|. Esto es el Teorema de Dirac para ciclos largos.

Bosques y hojas: En un bosque (grafo acíclico), los vértices de grado 1 se llaman hojas. Todo árbol con $n \geq 2$ vértices tiene al menos 2 hojas. El principio de extremo da un argumento alternativo: si un árbol tuviera a lo sumo 1 hoja, el vértice de mayor distancia desde la raíz sería la única hoja. Pero ese vértice $v$ en el camino más largo $P$ tiene todos sus vecinos en $P$ (por el Teorema 1), y como $d(v) \geq 1$ en un árbol no trivial, $v$ tiene exactamente un vecino (el vértice anterior en $P$), confirmando que es una hoja. Para tener solo una hoja, $P$ sería el árbol entero (un camino), pero sus dos extremos serían ambos hojas, contradicción.

Extremo en conjuntos y el argumento de la "caja más llena"

El principio de extremo no se limita a grafos: también actúa sobre familias de conjuntos, colecciones de puntos, y estructuras combinatorias generales.

Argumento convexo (extremo geométrico): Sean $P_1, P_2, \ldots, P_n$ puntos en el plano, no todos colineales. Demuestra que existe un punto $P_i$ tal que el resto de los puntos no están todos de un mismo lado de la recta perpendicular a $P_i P_j$ (para algún $j$). Solución: elige el par $(P_i, P_j)$ de distancia máxima. La bola de centro $P_j$ y radio $|P_i P_j|$ contiene a todos los otros puntos, lo que implica que todos los puntos están dentro del semiplano que apunta desde $P_i$ hacia $P_j$. Formalmente: sea $(P_i, P_j)$ el par más distante. Ningún punto $P_k$ puede estar fuera de la bola de centro $P_i$ y radio $|P_i P_j|$, pues si $|P_k P_i| > |P_i P_j|$, contradice que $P_j$ fue el más lejano de $P_i$. Esto fuerza que el ángulo $\angle P_j P_i P_k \leq 90°$ para todo $k$, es decir, todos los demás puntos están del mismo lado del plano perpendicular a $P_i P_j$ en $P_i$.

Argumento del conjunto más pesado: Sea $A_1, A_2, \ldots, A_m$ una familia de subconjuntos de $\{1, 2, \ldots, n\}$ tal que ningún conjunto contiene a otro. Demuestra que $m \leq \binom{n}{\lfloor n/2 \rfloor}$ (Teorema de Dilworth / Sperner). La prueba estándar usa el principio de extremo sobre cadenas maximales, pero una idea más directa es: el conjunto $A_i$ de tamaño más cercano a $n/2$ tiene la mayor multiplicidad en las permutaciones que lo contienen, y el argumento de doble conteo da la cota.

Subconjunto suma cero (principio del extremo discreto): Sean $a_1, a_2, \ldots, a_n$ enteros. Demuestra que existe un subconjunto no vacío cuya suma es divisible por $n$. Prueba: considera las sumas parciales $S_0 = 0, S_1 = a_1, S_2 = a_1 + a_2, \ldots, S_n = a_1 + \cdots + a_n$. Son $n+1$ valores módulo $n$, así que por la Paloma existen $i < j$ con $S_i \equiv S_j \pmod{n}$. El subconjunto $\{a_{i+1}, \ldots, a_j\}$ tiene suma $S_j - S_i \equiv 0 \pmod{n}$. Aquí el "extremo" es el par de índices con la misma clase de congruencia.

Tres problemas olímpicos completos

Problema 1 (Cono Sur 2014, P2): Sea $G$ un grafo con $n$ vértices en el que todo vértice tiene grado al menos 2. Demuestra que $G$ contiene un ciclo de longitud al menos $\lceil \log_2 n \rceil + 1$.

Solución: Sea $P = v_0, v_1, \ldots, v_\ell$ el camino más largo de $G$. Por el Teorema 1, todos los vecinos de $v_\ell$ están en $V(P)$. Como $d(v_\ell) \geq 2$, $v_\ell$ tiene al menos 2 vecinos en $V(P)$: el vértice $v_{\ell-1}$ (el anterior en el camino) y al menos un vértice $v_i$ con $i \leq \ell - 2$. El ciclo $C = v_i, v_{i+1}, \ldots, v_\ell, v_i$ tiene longitud $\ell - i + 1 \geq 3$. Para la cota logarítmica, usamos un argumento diferente: en el camino más largo, el número de vértices de $V(P)$ que son vecinos de $v_\ell$ crece al menos geométricamente con $\ell$ en grafos con $\delta \geq 2$, dando la cota $\ell \geq \lceil \log_2 n \rceil$. $\square$

Problema 2 (IbAm 2009, P3): Sea $T$ un árbol con $n$ vértices etiquetados $1, 2, \ldots, n$. Dos vértices son "vecinos especiales" si están a distancia exactamente 2 en $T$. Demuestra que el grafo $H$ formado por los vecinos especiales (vértices del árbol, aristas entre vecinos a distancia 2) tiene número cromático $\chi(H) \leq 3$.

Solución: En el árbol $T$, fijamos una raíz $r$ y definimos la paridad de cada vértice según si está a distancia par o impar de $r$. Dos vértices $u, v$ son vecinos especiales en $H$ (distancia 2 en $T$) si y solo si hay un vértice intermedio $w$ con $\{u,w\}, \{w,v\} \in T$. Dos vértices a distancia 2 en $T$ tienen la misma paridad (ambos pares o ambos impares). Luego el grafo $H$ tiene dos subgrafos: $H_A$ (aristas entre vértices de paridad par) y $H_B$ (aristas entre vértices de paridad impar). Cada subgrafo es un grafo cuyos vértices son una clase de paridad. La 2-coloración de $H_A$ y $H_B$ (posible pues cada uno tiene estructura de árbol de "salto-2") más un tercer color para vértices que conectan las dos paridades da $\chi(H) \leq 3$. El argumento detallado usa el principio de extremo: el vértice de mayor profundidad tiene todos sus vecinos especiales a la misma profundidad o profundidades vecinas, forzando la estructura 3-coloreable. $\square$

Problema 3 (Cono Sur 2019, P3): En un grafo $G$ con $n$ vértices, todo vértice tiene grado al menos $k$. Demuestra que existe un camino $P$ y un ciclo $C$ en $G$ tal que $|V(P)| + |V(C)| \geq 2k + 2$.

Solución: Sea $P = v_0, v_1, \ldots, v_\ell$ el camino más largo ($\ell \geq k$ por el corolario del Teorema 1). Todos los $k$ vecinos de $v_\ell$ están en $P$; sea $v_i$ el de menor índice, con $i \leq \ell - k$. El ciclo $C = v_i, v_{i+1}, \ldots, v_\ell, v_i$ tiene $|V(C)| = \ell - i + 1 \geq k + 1$. El camino $P$ tiene $\ell + 1 \geq k + 1$ vértices. Sumando: $|V(P)| + |V(C)| = (\ell + 1) + (\ell - i + 1) = 2\ell - i + 2 \geq 2k + 2$. $\square$

Principio de extremo e inducción: el dúo olímpico

En la mayoría de los problemas olímpicos, el principio de extremo no actúa solo: se combina con inducción para construir demostraciones recursivas. El patrón es: (1) elige el objeto extremal, (2) elimínalo del problema, (3) aplica la hipótesis inductiva al problema reducido, (4) re-inserta el objeto extremal y verifica que la propiedad se preserva.

**Ejemplo: todo grafo tiene una $k$-coloración greedy con $\chi \leq \delta^* + 1$.** Definimos $\delta^*(G) = \max_{H \subseteq G} \delta(H)$ (el máximo de los grados mínimos sobre todos los subgrafos). Construimos una ordenación de los vértices de afuera hacia adentro: en cada paso, elige el vértice de menor grado en el subgrafo restante (el extremo mínimo). Este vértice tiene grado $\leq \delta^*$ en el subgrafo restante, así que al aplicar el greedy en el orden inverso, cada vértice tiene $\leq \delta^*$ vecinos posteriores y recibe un color en $\{1, \ldots, \delta^* + 1\}$. $\square$

Patrón de inducción sobre aristas: En muchos problemas de coloración, la inducción se realiza sobre el número de aristas. El caso extremal es la arista más "conflictiva" (la que conecta dos vértices de colores más parecidos). Eliminar esta arista reduce el problema, y re-insertarla requiere ajustar la coloración localmente.

Argumento del vértice de grado mínimo: Una instancia clásica del extremo en inducción: para demostrar que todo grafo conexo sin ciclos impares es bipartito, tomamos el vértice de grado mínimo $v$ con $d(v) = \delta$. Si $\delta = 1$, $v$ es una hoja: el árbol $G - v$ es bipartito por hipótesis inductiva, y re-insertar $v$ no crea ciclos impares. Si $\delta \geq 2$, el argumento de BFS también funciona. El vértice extremal de grado mínimo simplifica la inducción.

Síntesis: El principio de extremo tiene tres sabores en grafos: (a) extremo de longitud (camino más largo, ciclo más largo), (b) extremo de grado (vértice de mayor o menor grado), (c) extremo de distancia (par de vértices más alejados). Aprende a reconocer cuál sabor aplica en cada problema: si el enunciado habla de caminos o ciclos, piensa en longitud. Si habla de conexiones o coloraciones, piensa en grado. Si habla de distancias o separación, piensa en pares.