Grafos: el lenguaje de las conexiones olímpicas

El problema que lo cambia todo

En un torneo de 6 equipos, cada par de equipos juega exactamente un partido. Demuestra que siempre existen 3 equipos tales que los tres se vencieron mutuamente (un ciclo de victorias) o los tres perdieron mutuamente (un ciclo de derrotas).

Si intentas verificar esto probando casos, te perderás en miles de configuraciones. La clave es que este problema habla de conexiones: quién vence a quién. Eso es exactamente la idea de un grafo. Con el lenguaje correcto, la solución se vuelve una demostración de media página.

Otro problema clásico: en una fiesta con $n$ personas, demuestra que al menos dos personas tienen exactamente el mismo número de amigos presentes. ¿Cómo atacas esto sin grafos? Con grafos, es un corolario inmediato del Lema del Apretón de Manos.

Estos dos problemas ilustran el poder de la teoría de grafos: transforma lenguaje cotidiano en estructura matemática sobre la cual podemos razonar con precisión.

Definiciones fundamentales y el Lema del Apretón de Manos

Un grafo $G = (V, E)$ consiste en un conjunto finito $V$ de vértices y un conjunto $E$ de aristas, donde cada arista es un par no ordenado $\{u,v\}$ con $u,v \in V$ y $u \neq v$.

El grado de un vértice $v$, denotado $d(v)$ o $\deg(v)$, es el número de aristas que inciden en $v$. Un grafo es **$k$-regular** si todo vértice tiene grado exactamente $k$.

Un camino de longitud $k$ es una secuencia de vértices distintos $v_0, v_1, \ldots, v_k$ tal que $\{v_i, v_{i+1}\} \in E$ para todo $i$. Un ciclo de longitud $k \geq 3$ es un camino cerrado $v_0, v_1, \ldots, v_{k-1}, v_0$ con todos los vértices distintos. Un grafo es conexo si entre todo par de vértices existe un camino.

Lema del Apretón de Manos: Para todo grafo $G = (V, E)$,

Demostración: Cada arista $\{u,v\} \in E$ contribuye exactamente 1 al grado de $u$ y exactamente 1 al grado de $v$. Al sumar todos los grados, cada arista se cuenta exactamente dos veces. Por tanto $\sum_{v \in V} d(v) = 2|E|$. $\square$

Corolario: En todo grafo, el número de vértices de grado impar es par.

Prueba del corolario: Si $\sum d(v) = 2|E|$ es par, y separamos la suma en vértices de grado par e impar, la contribución de los vértices de grado par es par, luego la contribución de los de grado impar también debe ser par. Esto fuerza que la cantidad de vértices de grado impar sea par. $\square$

Aplicación al problema de la fiesta: Si hay $n$ personas en la fiesta, los posibles grados van de $0$ a $n-1$. Pero si alguien conoce a todos ($d = n-1$), es imposible que alguien no conozca a nadie ($d = 0$). Luego hay a lo más $n-1$ valores posibles de grado para $n$ personas. Por el Principio de la Paloma, dos personas tienen el mismo grado. $\square$

Árboles: el esqueleto de los grafos

Un árbol es un grafo conexo sin ciclos. Los árboles son fundamentales en combinatoria olímpica porque son los grafos "mínimamente conexos": quitar cualquier arista desconecta el grafo.

Teorema: Todo árbol con $n$ vértices tiene exactamente $n-1$ aristas.

Prueba por inducción: Para $n=1$ el árbol consiste en un único vértice sin aristas; $1-1=0$. Supongamos que todo árbol con $n-1$ vértices tiene $n-2$ aristas. Sea $T$ un árbol con $n \geq 2$ vértices. Como $T$ es finito y acíclico, tiene al menos un vértice de grado 1 (llamado hoja). Sea $v$ una hoja y sea $e$ la única arista incidente en $v$. El grafo $T - v$ (obtenido al eliminar $v$ y $e$) sigue siendo conexo (la única arista eliminada incidía en $v$, que tenía grado 1) y sigue siendo acíclico. Por hipótesis de inducción, $T - v$ tiene $n-2$ aristas. Entonces $T$ tiene $(n-2)+1 = n-1$ aristas. $\square$

Prueba alternativa por doble conteo: En cualquier grafo conexo con $n$ vértices y $m$ aristas, $m \geq n-1$ (se necesitan al menos $n-1$ aristas para conectar $n$ vértices). En un árbol, añadir cualquier arista crea exactamente un ciclo, lo que implica que no puede haber aristas "extra": $m = n-1$.

Un árbol generador (o spanning tree) de un grafo conexo $G$ es un subgrafo que contiene todos los vértices de $G$ y es un árbol. Todo grafo conexo tiene al menos un árbol generador. En olimpiadas, los árboles generadores aparecen cuando queremos "reducir" un grafo conexo a su estructura esencial.

Ejemplo olímpico (Cono Sur 2008, adaptado): Se conectan $n$ ciudades con carreteras formando un grafo conexo. Se quiere dejar exactamente $n-1$ carreteras de forma que siga siendo posible viajar entre cualquier par de ciudades. Demuestra que esto siempre es posible y que el resultado es único si además pedimos que no haya circuitos. Solución: basta tomar cualquier árbol generador del grafo, que tiene $n-1$ aristas y es conexo. Si además pedimos que no haya circuitos, la estructura es exactamente un árbol, que es única en esa propiedad.

Grafos bipartitos y el argumento de 2-coloración

Un grafo $G = (V, E)$ es bipartito si el conjunto de vértices puede particionarse en dos subconjuntos $A$ y $B$ (la bipartición) tal que toda arista conecta un vértice en $A$ con uno en $B$. Es decir, no hay aristas entre dos vértices del mismo lado.

Teorema de Caracterización: Un grafo es bipartito si y solo si no contiene ciclos de longitud impar.

**Demostración ($\Rightarrow$):** Sea $G$ bipartito con bipartición $(A, B)$. Todo camino alterna entre $A$ y $B$. Por tanto, cualquier ciclo $v_0, v_1, \ldots, v_{k-1}, v_0$ alterna entre $A$ y $B$: si $v_0 \in A$, entonces $v_1 \in B$, $v_2 \in A$, etc. Para que el ciclo cierre, necesitamos $v_0$ y $v_{k-1}$ en lados distintos, lo que ocurre exactamente cuando $k$ es par.

**Demostración ($\Leftarrow$):** Supongamos que $G$ no tiene ciclos impares. Sea $G$ conexo (si no, aplicamos el argumento a cada componente). Fijamos un vértice $r$ y definimos $A$ como el conjunto de vértices a distancia par de $r$, y $B$ como los de distancia impar. Afirmamos que toda arista conecta un vértice en $A$ con uno en $B$. Si hubiera una arista $\{u,v\}$ con $u, v \in A$ (ambos a distancia par de $r$), los caminos $r \to u$, la arista $u$-$v$, y $v \to r$ formarían un ciclo de longitud impar, contradicción. $\square$

La técnica olímpica de 2-coloración: Cuando un problema involucra una partición en dos clases con cierta propiedad de "incompatibilidad" (dos objetos del mismo tipo no pueden ser adyacentes, o similares), piensa en grafos bipartitos. El argumento es: construye un grafo donde los vértices son los objetos y conecta dos objetos si son "incompatibles". La condición del problema puede reformularse como: ¿es este grafo bipartito? Si sí, la 2-coloración da la partición deseada.

Ejemplo: Un tablero $m \times n$ se colorea con los colores blanco y negro como un tablero de ajedrez. Muestra que si $m$ y $n$ son impares, es imposible cubrir exactamente todos los casilleros con dominós $1 \times 2$. Solución: el tablero de ajedrez define un grafo bipartito $G$ donde cada casillero es un vértice y cada dominó potencial es una arista. Como $mn$ es impar, el número de casilleros blancos y negros difiere en 1. Un recubrimiento por dominós corresponde a un matching perfecto en $G$, pero en un grafo bipartito, si los dos lados tienen tamaños distintos, no hay matching perfecto (por el Teorema de Hall). Contradicción.

Ramsey: orden inevitable en el caos

La teoría de Ramsey estudia cuándo, en una estructura suficientemente grande, cierto patrón es inevitable. El resultado más famoso a nivel olímpico es $R(3,3) = 6$.

**Teorema: $R(3,3) = 6$.** En toda 2-coloración (rojo/azul) de las aristas del grafo completo $K_6$, existe un triángulo monocromático (tres vértices mutuamente conectados por aristas del mismo color). Además, existe una 2-coloración de $K_5$ sin triángulo monocromático, por lo que 6 es el mínimo.

**Demostración de que $K_6$ funciona:** Sea $v$ un vértice de $K_6$. Tiene 5 aristas a los otros vértices. Por el Principio de la Paloma, al menos $\lceil 5/2 \rceil = 3$ de estas aristas tienen el mismo color; digamos rojo. Sean $a, b, c$ los tres vértices conectados a $v$ por aristas rojas. Si cualquiera de las aristas $\{a,b\}$, $\{a,c\}$ o $\{b,c\}$ es roja, junto con las aristas $v$-$a$ o $v$-$b$ o $v$-$c$ forma un triángulo rojo. Si ninguna es roja, las tres son azules y $\{a,b,c\}$ forman un triángulo azul. $\square$

**Demostración de que $K_5$ no alcanza:** Colorea $K_5$ así: los vértices son $1,2,3,4,5$ en un pentágono. Las aristas del pentágono son rojas y las diagonales son azules. Verificación: ningún triángulo tiene las 3 aristas del mismo color (es el grafo de Petersen en disfraz).

Conexión con el problema del torneo: El problema inicial de la fiesta se resuelve exactamente con $R(3,3) = 6$: coloreamos la arista $\{u,v\}$ de rojo si $u$ le ganó a $v$, y de azul si $v$ le ganó a $u$. Un triángulo rojo es un ciclo de victorias; un triángulo azul, un ciclo de derrotas.

Números de Ramsey generales: $R(s,t)$ es el menor $n$ tal que toda 2-coloración de $K_n$ contiene un clique rojo de tamaño $s$ o un clique azul de tamaño $t$. Los valores conocidos son escasos: $R(3,3)=6$, $R(3,4)=9$, $R(3,5)=14$, $R(4,4)=18$. La búsqueda de $R(5,5)$ sigue abierta.

Estrategia olímpica: traducir, invariantear, colorear

La teoría de grafos olímpica gira en torno a tres movimientos: traducción, invariantes y coloración.

Paso 1 — Traducción. Lee el problema e identifica: ¿hay objetos (personas, casilleros, equipos) con relaciones entre ellos (amistades, adjacencias, resultados)? Si la respuesta es sí, define $V$ (los objetos) y $E$ (las relaciones) y dibuja el grafo. Un buen grafo convierte lenguaje vago en estructura precisa.

Paso 2 — Invariantes. Busca cantidades que se conservan o que tienen cota fija. Los candidatos más comunes son: la paridad de $\sum d(v) = 2|E|$ (siempre par), el número de componentes conexas, la paridad de los ciclos (bipartito iff sin ciclos impares), el grado máximo y mínimo. Muchos problemas de existencia se resuelven mostrando que cierto invariante no puede alcanzar el valor pedido.

Paso 3 — Coloración. Si la condición del problema admite una partición natural en dos clases, intenta 2-colorear los vértices o las aristas. Si llegas a una contradicción asumiendo que no hay monocromático, eso prueba la existencia. El Lema del Apretón de Manos y el argumento de Ramsey son instancias de este principio.

Vértice extremal. Una técnica transversal: elige el vértice de mayor grado (o menor, o más alejado de un punto fijo). Sus vecinos heredan propiedades fuertes. Esta técnica, combinada con inducción sobre $|V|$ o $|E|$, resuelve muchos problemas de coloración y de existencia de subgrafos.

Ejemplo de síntesis (IbAm 2016, P2, adaptado): En un grafo donde todo vértice tiene grado al menos $k$, demuestra que existe un camino de longitud al menos $k$. Solución: toma el camino más largo $v_0, v_1, \ldots, v_\ell$. Todos los vecinos de $v_\ell$ están en el camino (si hubiera un vecino fuera, extenderíamos el camino). Como $d(v_\ell) \geq k$, hay al menos $k$ vecinos de $v_\ell$ en el camino, luego $\ell \geq k$.

Resumen de herramientas: (1) Lema del Apretón de Manos, (2) Caracterización de bipartitos, (3) Fórmula de árboles $|E| = n-1$, (4) $R(3,3)=6$, (5) Vértice extremal con inducción. Estas cinco herramientas resuelven la mayoría de los problemas de grafos en olimpiadas Cono Sur e Iberoamericana.