SE CIERRA POR FIN UN ROMPECABEZAS DE GRAFOS DE LOS AÑOS SESENTA

Tome unos cuantos puntos y una algunos pares con líneas: los matemáticos llaman a esto un grafo, a los puntos sus vértices y a las líneas sus aristas. Un ciclo es un bucle cerrado que recorre vértices distintos y vuelve a su punto de partida. Una pregunta natural es si las aristas de un grafo pueden repartirse —usando cada arista exactamente una vez— en ciclos.

La respuesta se conoce desde hace mucho, como recuerda el artículo: es posible exactamente cuando cada vértice toca un número par de aristas. Estos grafos se llaman eulerianos. La siguiente pregunta es cuántos ciclos hacen falta. Y para los grafos en los que los ciclos no bastan, también se admiten aristas sueltas como piezas.

La conjetura

En los años sesenta, Erdős y Gallai conjeturaron que las aristas de todo grafo con n vértices pueden repartirse en un número de ciclos y aristas sueltas como mucho proporcional a n, lo que se escribe O(n). Erdős la incluyó en varias de sus colecciones de problemas abiertos. Una conjetura relacionada, de Hajós, pide como mucho (n − 1)/2 ciclos en todo grafo euleriano.

Lo lineal es lo mejor que cabe esperar: Erdős demostró que algunos grafos necesitan unas 1,5 n piezas. La cuestión era si siempre basta con alguna constante multiplicada por n.

Cincuenta años de cotas que avanzan a paso lento

Los propios Erdős y Gallai se dieron cuenta de un método sencillo: quitar repetidamente el ciclo más largo. Da unas n log n piezas y, según el artículo, esa siguió siendo la mejor cota general durante casi cincuenta años. Más recientemente, Conlon, Fox y Sudakov la redujeron a n log log n, y después Bucić y Montgomery a n log* n, donde log* n —el número de veces que hay que tomar un logaritmo para bajar de uno— crece de forma inimaginablemente lenta. Estos enfoques funcionaban por rondas, y cada ronda costaba unos n ciclos, de modo que el número de rondas siempre se colaba en la cuenta final. La conjetura también se había demostrado para familias especiales, como los grafos aleatorios.

Pesos que pagan los bucles

Jaehoon Kim, del KAIST en Corea del Sur, demuestra ahora la conjetura: existe una constante fija C tal que todo grafo con n vértices se reparte en como mucho Cn ciclos y aristas. Como corolario, la conjetura de Hajós se cumple salvo un factor constante.

La demostración abandona las rondas. Un único procedimiento quita ciclos y aristas de uno en uno, y el total queda controlado por dos cantidades que se mantienen, cada una, por debajo de una constante por n.

• Un potencial basado en los grados. Cada vértice recibe un peso que disminuye con su número de aristas, aproximadamente 1 / (grado × log² grado). Un ciclo es pesado si los pesos de sus vértices suman al menos 1. Quitar un ciclo pesado reduce un «potencial» global en al menos 1, y ese potencial empieza siendo, como mucho, una constante por n. Así que los ciclos pesados solo pueden quitarse O(n) veces.
• El número de vértices. Cuando no queda ningún ciclo pesado, el grafo es «ligero», y el principal teorema nuevo muestra que un grafo ligero con grados grandes debe contener una región densa y casi cerrada. Esa región se reparte en un número de ciclos y aristas proporcional a su tamaño, tras lo cual al menos una quincuagésima parte de sus vértices se queda con como mucho dos aristas y sale del juego para siempre. Como cada vértice solo puede salir una vez, esta parte también cuesta O(n).

Dentro de las partes densas del grafo, los trozos de camino se cierran en un único ciclo mediante caminos de unión que pasan por «expansores»; una coloración aleatoria mantiene separados los caminos de unión de un mismo ciclo. — Figura 3, Kim (2026), arXiv:2610.07840.

Para repartir esas regiones densas, la demostración amplía las herramientas de Bucić y Montgomery basadas en «expansores» robustos —grafos en los que todo conjunto de vértices tiene muchos vecinos— y colorea los vértices al azar para que los caminos de conexión de un mismo ciclo nunca choquen.

Lo que sigue abierto

La constante C es enorme, y el autor no intentó optimizarla. Encontrar la mejor constante —al menos 1,5— sigue siendo un problema abierto, al igual que la conjetura exacta de Hajós y una conjetura relacionada de Gallai sobre la división de grafos en caminos. El truco de los pesos solo necesita pesos cuya suma converja, y el autor sugiere que podría servir en otros problemas de descomposición.

Se trata de un preprint de un solo autor, aún no verificado mediante revisión por pares.

Conflicto de intereses. El autor declara que utilizó extensamente ChatGPT (OpenAI) y Claude (Anthropic) para desarrollar los argumentos y preparar el texto y las figuras, y que verificó todos los resultados y asume la plena responsabilidad del artículo. El texto que está leyendo también lo ha escrito Claude.