UN LÍMITE PARA LAS REDES, DEMOSTRADO YA PARA CUALQUIER TAMAÑO
Tomemos unos cuantos puntos y unamos algunos pares con líneas. Los matemáticos llaman a esto un grafo: los puntos son sus vértices, las líneas sus aristas, y la distancia entre dos vértices es el menor número de aristas necesario para ir de uno a otro. Añadamos ahora dos reglas. Todo par de vértices debe estar a distancia 2 como mucho: unidos directamente o a través de un vecino común. Y no puede sobrar ninguna arista: si se borra una sola, algún par queda a más de dos pasos. Un grafo así se llama crítico de diámetro 2. ¿Cuántas aristas puede tener?
El techo de Mantel y una conjetura más audaz
En 1907, Mantel demostró que un grafo de n vértices sin triángulos —sin tres vértices unidos todos entre sí— tiene como mucho ⌊n²/4⌋ aristas: n al cuadrado dividido entre cuatro, redondeado hacia abajo a un número entero. Solo un grafo alcanza ese techo, el grafo bipartito completo equilibrado: dos grupos de tamaños lo más iguales posible, con cada vértice de uno unido a cada vértice del otro y ninguna arista dentro de un mismo grupo.
Todo grafo sin triángulos al que no se le puede añadir una arista más sin crear un triángulo es crítico de diámetro 2. Lo contrario no se cumple: algunos grafos críticos de diámetro 2 contienen triángulos.
Un grafo crítico de diámetro 2 con 7 vértices y 9 aristas, que contiene el triángulo v1v3v5. Borrar v1v3 destruye la única ruta de dos pasos entre v2 y v3; borrar una arista fuera del triángulo deja a sus extremos sin ruta de dos pasos. — Figura 1, Das & Fox (2026), arXiv:2610.39032.
La conjetura era que los triángulos no aportan nada: un grafo crítico de diámetro 2 con n vértices sigue teniendo como mucho ⌊n²/4⌋ aristas, y el grafo bipartito completo equilibrado sigue siendo el único que lo alcanza. El teorema de Mantel se deduciría como caso particular. Para los 7 vértices de la figura, el techo es de 12 aristas.
Una torre de doses
Según Erdős, tal como lo relata Zoltán Füredi, la cuestión se remonta a trabajos de Ore en la década de 1960. Ján Plesník formuló la cota de aristas como conjetura en 1975; Murty y Simon la propusieron de forma independiente y añadieron que el grafo bipartito completo equilibrado es el único caso extremo; de ahí la conjetura de Murty-Simon. En las décadas de 1970 y 1980, fueron bajando cotas de la forma c·n², con c cada vez más cerca de 1/4.
En 1992, Füredi demostró la conjetura para todo n suficientemente grande, con métodos de regularidad, herramientas derivadas del lema de regularidad de Szemerédi. El precio era el tamaño inicial: n tenía que ser al menos una torre de doses de altura aproximada 10¹⁴, es decir, 2 elevado a 2 elevado a 2…, calculado de arriba abajo (cada 2 elevado a todo lo que tiene encima), con unos 10¹⁴ doses apilados. Por debajo de ese tamaño, solo se habían resuelto familias especiales de grafos.
Aristas frente a aristas ausentes
La nueva demostración, de Sanjana Das y Jacob Fox, del Departamento de Matemáticas de la Universidad de Stanford, funciona para todo n a partir de 3. Usa un emparejamiento maximal: un conjunto de aristas, sin dos que compartan vértice, al que no se puede añadir ninguna otra arista sin que dos de ellas se toquen. Un emparejamiento sobre n vértices tiene como mucho ⌊n/2⌋ aristas.
El lema clave: en un grafo crítico de diámetro 2, para cualquier emparejamiento maximal, las aristas que quedan fuera del emparejamiento nunca son más numerosas que las no aristas, los pares de vértices que no están unidos. El resto es aritmética. El doble del número de aristas es como mucho el número de pares más el tamaño del emparejamiento. Con 10 vértices: 45 pares más como mucho 5 aristas del emparejamiento dan 50, luego como mucho 25 aristas. Para todo n, esa suma es exactamente el doble del techo de Mantel.
El propio lema es una contabilidad minuciosa. Una no arista es crítica si una única ruta de dos pasos une sus extremos, como ocurre con las doce no aristas de la figura 1. Los autores asocian cada no arista crítica a las dos aristas de su ruta y dividen la red resultante en piezas conexas. Una pieza contiene como mucho una arista más que no aristas críticas, y cada pieza con ese excedente debe pagarse con una no arista no crítica. Para encontrarlas, los autores usan salidas por intercambio (switch exits): se toma una arista o una no arista crítica de la pieza y se cambia uno de sus extremos por la pareja de ese extremo en el emparejamiento. Cada no arista no crítica se reclama como mucho dos veces, cada pieza con excedente hace al menos dos reclamaciones, y la cuenta cuadra.
Quién encontró qué
«Esta demostración la encontró en su mayor parte una IA, concretamente GPT-5.6 Sol, el 11 de agosto de 2026», escriben los autores en una breve declaración sobre la IA. El modelo encontró una demostración completa de la cota ⌊n²/4⌋, que ellos simplificaron. Para un número par de vértices, demostró también que el grafo bipartito completo equilibrado es el único caso extremo, apoyándose en un resultado demostrado por Sumner sobre los grafos en los que todo emparejamiento maximal es perfecto, es decir, cubre todos los vértices.
Con un número impar de vértices, ningún emparejamiento es perfecto, y en muchos grafos todo emparejamiento maximal deja fuera exactamente un vértice: el argumento del modelo no podía adaptarse. Los autores encontraron otra demostración del caso de igualdad, válida para todo n, y redactaron ellos mismos el artículo; una revisión final con GPT-6 Astra dio lugar a «unas pocas correcciones menores». El artículo es una prepublicación, aún sin revisión por pares, y no menciona ninguna versión del argumento verificada por ordenador.
De vuelta a 1907
Si un grafo iguala el techo, la desigualdad clave es una igualdad para todo emparejamiento maximal. Eligiendo los emparejamientos con astucia, los autores demuestran que un grafo así es o bien una estrella —un vértice unido a todos los demás, y nada más— o bien no tiene ninguna no arista crítica. En un grafo crítico de diámetro 2, toda arista de un triángulo está en alguna ruta crítica, así que no tener no aristas críticas significa no tener triángulos; una estrella tampoco tiene ninguno. Un grafo que iguala el techo es, por tanto, un grafo sin triángulos, y el último paso es el teorema que la conjetura pretendía reforzar: el resultado de Mantel de 1907, que deja al grafo bipartito completo equilibrado solo en el techo.