El problema de Turán: máximo de aristas sin $K_{r+1}$

El problema que lo origina todo: ¿cuántas amistades evitan un cuarteto de amigos?

En 1941, el matemático húngaro Pál Turán, internado en un campo de trabajo forzado durante la Segunda Guerra Mundial, encontró tiempo para pensar en el siguiente problema: ¿cuál es el mayor número de aristas que puede tener un grafo de $n$ vértices sin contener $K_3$ —un triángulo— como subgrafo?

Esta pregunta, aparentemente simple, dio origen a la teoría extremal de grafos: la rama de la combinatoria que estudia las configuraciones que maximizan o minimizan parámetros globales de un grafo bajo la restricción de evitar ciertos subgrafos.

Turán respondió la pregunta para todos los cliques $K_{r+1}$, no solo triángulos. Su respuesta es elegante: el grafo extremal —el que tiene más aristas sin $K_{r+1}$— es el **grafo completo $r$-partido equilibrado**, que hoy llevael su nombre. Comenzamos por el caso motivador $K_3$.

Sea $G$ un grafo con $n$ vértices y sin triángulos. ¿Cuántas aristas puede tener? La respuesta la dio en 1907 Willem Mantel, antes que Turán: a lo sumo $\lfloor n^2/4 \rfloor$. La demostración es una joya de elegancia.

El Teorema de Mantel: grafos sin triángulo

Sea $G$ un grafo con $n$ vértices y $e$ aristas, y supongamos que $G$ es libre de triángulos ($K_3$-free). Queremos acotar $e$ desde arriba.

Prueba por suma de grados. Para cada arista $\{u,v\} \in E(G)$, la condición libre de triángulos implica que los vecinos de $u$ y los de $v$ son disjuntos: ningún vértice $w$ puede ser adyacente a ambos, pues formaría el triángulo $\{u,v,w\}$. Por tanto $d(u) + d(v) \le n$ para toda arista $\{u,v\}$.

Sumamos esta desigualdad sobre todas las aristas: $\displaystyle\sum_{\{u,v\}\in E} (d(u)+d(v)) \le n\cdot e$. El lado izquierdo es $\sum_v d(v)^2$ (cada vértice $v$ contribuye $d(v)$ por cada una de sus $d(v)$ aristas incidentes). Por la desigualdad de Cauchy-Schwarz, $\sum_v d(v)^2 \ge \tfrac{1}{n}\bigl(\sum_v d(v)\bigr)^2 = \tfrac{(2e)^2}{n}$.

Combinando ambas desigualdades: $\tfrac{4e^2}{n} \le n\cdot e$, lo que simplifica a $e \le \tfrac{n^2}{4}$. Más precisamente, $e \le \lfloor n^2/4 \rfloor$.

La igualdad se alcanza en el grafo bipartito completo equilibrado $K_{\lfloor n/2\rfloor,\lceil n/2\rceil}$, que no contiene triángulos (es bipartito) y tiene exactamente $\lfloor n^2/4 \rfloor$ aristas. Este es el grafo de Turán $T(n,2)$.

El Teorema de Turán: enunciado general

El Teorema de Mantel es el caso particular $r=2$ de un resultado mucho más general que Turán estableció para cliques de cualquier tamaño.

Definición. El número extremal $\mathrm{ex}(n, K_{r+1})$ es el máximo número de aristas que puede tener un grafo de $n$ vértices sin contener $K_{r+1}$ como subgrafo.

Teorema de Turán (1941). Para todo $n \ge 1$ y todo $r \ge 1$,

$\mathrm{ex}(n, K_{r+1}) = |E(T(n,r))|$

donde $T(n,r)$ es el grafo completo $r$-partido equilibrado, es decir, el grafo completo $r$-partido cuyos $r$ partes tienen tamaños $\lfloor n/r \rfloor$ o $\lceil n/r \rceil$ (difieren en a lo sumo 1). Además, $T(n,r)$ es el único grafo extremal: si $G$ tiene $n$ vértices, no contiene $K_{r+1}$ y $|E(G)| = |E(T(n,r))|$, entonces $G \cong T(n,r)$.

El número de aristas de $T(n,r)$ es $|E(T(n,r))| = \left(1 - \tfrac{1}{r}\right)\tfrac{n^2}{2} + O(n)$. La fórmula exacta la calcularemos en la Lección 2.2.

Prueba por borrado de vértices: inducción elegante

Presentamos la demostración más accesible del Teorema de Turán, basada en el principio de inducción con un argumento de borrado.

**Prueba por inducción sobre $n$.** Para $n \le r$, todo grafo de $n$ vértices es $K_{r+1}$-free (no hay suficientes vértices para $K_{r+1}$), y el grafo completo $K_n$ maximiza las aristas. El grafo completo $K_n$ para $n \le r$ es precisamente $T(n,r)$ (todas las partes tienen tamaño 0 o 1 y no hay aristas entre vértices de la misma parte), así que la base vale.

Para $n > r$: sea $G$ un grafo $K_{r+1}$-free con $n$ vértices y el máximo número de aristas. Como $G$ es $K_{r+1}$-free con más de $r$ vértices, hay al menos un conjunto de $r$ vértices que forman $K_r$ (si no, $G$ sería $K_r$-free y tendría menos aristas que $T(n,r-1) < T(n,r)$, contradiciendo la maximalidad —aunque este paso requiere justificación adicional; una ruta más limpia usa el argumento de Zykov que presentamos en la Lección 2.2).

La prueba por Zykov es la más completa. Para esta lección, damos el argumento de sustitución por promedio, que es suficiente para olimpiadas.

Prueba por sustitución por promedio. Sea $G$ un grafo $K_{r+1}$-free de $n$ vértices con $e$ aristas máximas. Si $G$ no es $r$-partido, entonces hay dos vértices $u, v$ en la misma parte (en el sentido: que no son adyacentes). Considera el grafo $G'$ obtenido de $G$ tomando uno de ellos, digamos $v$, y reemplazando $v$ por una copia de $u$: el nuevo vértice $v'$ es adyacente exactamente a los mismos vértices que $u$. Si $d(u) \ge d(v)$, entonces $G'$ tiene al menos tantas aristas como $G$, sigue siendo $K_{r+1}$-free (ejercicio: verificar), y un vértice extra tiene el mismo vecindario que $u$.

Iterando este proceso de "igualar vecindades", llegamos a un grafo en el que los vértices se dividen en clases de equivalencia por vecindad, formando exactamente un grafo $r$-partido completo. El equilibrio entre las partes sigue de que desbalancear dos partes (mover un vértice de la más grande a la más pequeña) siempre aumenta el número de aristas o lo preserva.

¿Por qué el grafo de Turán es extremal? La intuición geométrica

El grafo de Turán $T(n,r)$ evita $K_{r+1}$ de forma "máximamente densa". Para verlo, pensemos en la estructura del problema: queremos tantas aristas como sea posible sin crear $K_{r+1}$.

La restricción "$K_{r+1}$-free" es equivalente a: el número de clique de $G$ es a lo sumo $r$ ($\omega(G) \le r$). Para maximizar aristas con esta restricción, la estrategia óptima es crear $r$ grupos de vértices y conectar todo con todo entre distintos grupos, pero nada dentro de un grupo. Esto da exactamente el grafo $r$-partido completo.

El equilibrio entre los tamaños de las partes es la clave: si las partes tienen tamaños $n_1, n_2, \ldots, n_r$ con $\sum n_i = n$, el número de aristas es $\sum_{i<j} n_i n_j = \tfrac{1}{2}\bigl[(\sum n_i)^2 - \sum n_i^2\bigr] = \tfrac{n^2 - \sum n_i^2}{2}$. Para maximizar esto, hay que minimizar $\sum n_i^2$ sujeto a $\sum n_i = n$, lo cual —por la desigualdad entre medias cuadrática y aritmética— se logra cuando todos los $n_i$ son iguales (o difieren en a lo sumo 1 cuando $r \nmid n$).

Esto conecta el Teorema de Turán con la desigualdad AM-QM: la optimalidad del equilibrio entre partes no es accidental, es una instancia de la convexidad de $x^2$.

El Teorema de Turán en acción: tres aplicaciones

Aplicación 1: El teorema de la amistad. Un grafo de "amistad" es un grafo $G$ de $n$ vértices donde todo par de vértices tiene exactamente un amigo común. El Teorema de la Amistad (Erdős, Rényi, Sós, 1966) afirma que tal grafo existe si y solo si $G$ consiste en $k$ triángulos pegados por un vértice central (el "grafo de libro" $B_k$). La idea clave de la prueba: como el grafo de amistad es muy denso (o bien $K_3$-free, lo que junto con la condición de amigo único fuerza estructura muy especial), el Teorema de Turán ayuda a discriminar los casos posibles.

Aplicación 2: Grafos libres de triángulo en grafos densos. En un grafo con $n$ vértices y $m > n^2/4$ aristas, el Teorema de Turán (caso $r=2$) garantiza que existe un triángulo. Esto es extremadamente útil en olimpiadas: si se pide demostrar que en cierto grafo denso aparece un triángulo, verificar que $m > n^2/4$ es suficiente.

Aplicación 3: Cotas para incidencias punto-recta. En la combinatoria geométrica, el número de incidencias entre $n$ puntos y $n$ rectas en el plano real está acotado por el Teorema de Szemerédi-Trotter, cuya prueba usa el Teorema de Turán como herramienta auxiliar para evitar configuraciones con muchas incidencias concentradas.

En problemas olímpicos, la señal típica de que se necesita Turán es: "dado un grafo/hipógrafo/relación entre $n$ objetos con ciertas restricciones de independencia, acota el número de relaciones (aristas) o demuestra la existencia de una configuración completa de tamaño $r+1$". El primer reflejo debe ser calcular si las condiciones del enunciado implican que el número de aristas supera $|E(T(n,r))|$.