Funda doble para bicicleta

En matemáticas de teoría de grafos , una doble cobertura cíclica es un conjunto de ciclos en un grafo no dirigido que, en conjunto, incluyen cada arista del grafo exactamente dos veces. Por ejemplo, para cualquier grafo poliédrico , las caras de un poliedro convexo que representa el grafo proporcionan una doble cobertura cíclica del mismo: las aristas de cada cara forman un ciclo y cada arista pertenece exactamente a dos caras y, por lo tanto, a dos de estos ciclos.

Es un problema planteado en la década de 1970 por WT Tutte , ^{[ 1 ]} Itai y Rodeh, ^{[ 2 ]} George Szekeres ^{[ 3 ]} y Paul Seymour ^{[ 4 ]} y conocido como la conjetura de la doble cobertura cíclica , que trata sobre si todo grafo sin puentes tiene una doble cobertura cíclica. La conjetura puede formularse de forma equivalente en términos de incrustaciones de grafos , y en ese contexto también se conoce como la conjetura de la incrustación circular .

El 10 de julio de 2026, OpenAI publicó una preimpresión que afirmaba una resolución positiva de la conjetura, ^{[ 5 ] [ 6 ]} cuya prueba, según afirman, fue generada por GPT-5.6 , su gran modelo de lenguaje .

Un ciclo es un subgrafo conexo cuyos vértices tienen todos grado 2. En particular, una sola arista, recorrida de un lado a otro, no se considera un ciclo. Un puente en un grafo es una arista cuya eliminación aumenta el número de componentes conexas.

La formulación habitual de la conjetura de la doble cobertura cíclica pregunta si todo grafo no dirigido finito sin puentes admite una colección de ciclos tal que cada arista del grafo esté contenida en exactamente dos de los ciclos.

El requisito de que el grafo no tenga puentes es una condición necesaria obvia para que exista una doble cobertura, ya que un puente no puede pertenecer a ningún ciclo. Algunos grafos, como los grafos cíclicos y los grafos cactus sin puentes , solo tienen dobles coberturas que utilizan el mismo ciclo dos veces, por lo que este tipo de duplicación está permitida en una doble cobertura cíclica. Esto significa que, en realidad, buscamos un multiconjunto de ciclos tal que cada arista del grafo pertenezca a exactamente dos elementos del multiconjunto.

OpenAI publicó una propuesta de prueba de tres páginas de la conjetura ^{[ 5 ]} junto con la instrucción de dos páginas utilizada para generarla. ^{[ 7 ]} La ​​instrucción se le dio al modelo de lenguaje grande GPT-5.6 Sol Ultra, indicándole que empleara "hasta 64 agentes concurrentes", "usara agentes adversarios en todo momento" para verificar las pruebas candidatas y "dedicara al menos 8 horas a esto". ^{[ 7 ]} El equipo de OpenAI también publicó una formalización de la prueba en Lean . ^{[ 8 ]}

La demostración utiliza una reducción de Jaeger (1985) mencionada más adelante, a saber, que es suficiente demostrar la conjetura para multigrafos sin bucles cuyos vértices tienen grado 3. Además, la demostración utiliza el hecho de que todo grafo sin puentes admite un cero en ninguna parte.${\displaystyle {\mathbb {F}}_{2}^{3}}$-flujo, que fue establecido independientemente por Jaeger (1976) y Kilpatrick (1975).

Un snark es un caso especial de grafo sin puentes, con las propiedades adicionales de que cada vértice tiene exactamente tres aristas incidentes (es decir, el grafo es cúbico ) y que no es posible particionar las aristas del grafo en tres emparejamientos perfectos (es decir, el grafo no tiene coloración de 3 aristas y, según el teorema de Vizing, tiene índice cromático 4). Resulta que los snarks constituyen el único caso difícil de la conjetura de la doble cobertura cíclica: si la conjetura es cierta para los snarks, es cierta para cualquier grafo. ^{[ 9 ]}

Jaeger (1985) observa que, en cualquier posible contraejemplo mínimo a la conjetura de la doble cobertura cíclica, todos los vértices deben tener tres o más aristas incidentes. Un vértice con una sola arista incidente forma un puente, mientras que si dos aristas inciden en un vértice, se pueden contraer para formar un grafo más pequeño, de modo que cualquier doble cobertura de este grafo se extienda a uno de los vértices del grafo original. Por otro lado, si un vértice v tiene cuatro o más aristas incidentes, se pueden "separar" dos de ellas eliminándolas del grafo y reemplazándolas por una sola arista que conecte sus otros dos extremos, conservando la ausencia de puentes en el grafo resultante. De nuevo, una doble cobertura del grafo resultante se puede extender de forma directa a una doble cobertura del grafo original: cada ciclo del grafo separado corresponde a un ciclo del grafo original o a un par de ciclos que convergen en v . Por lo tanto, todo contraejemplo mínimo debe ser cúbico. Pero si un grafo cúbico puede tener sus aristas coloreadas con tres colores (por ejemplo, rojo, azul y verde), entonces el subgrafo de aristas rojas y azules, el subgrafo de aristas azules y verdes, y el subgrafo de aristas rojas y verdes forman cada uno una colección de ciclos disjuntos que, en conjunto, cubren todas las aristas del grafo dos veces. Por lo tanto, todo contraejemplo mínimo debe ser un grafo cúbico sin puentes que no se puede colorear con tres colores en sus aristas, es decir, un snark. ^{[ 9 ]}

Un posible ataque al problema de la doble cobertura cíclica sería demostrar que no puede existir un contraejemplo mínimo, probando que cualquier grafo contiene una configuración reducible , un subgrafo que puede ser reemplazado por un subgrafo más pequeño de manera que se preserve la existencia o no existencia de una doble cobertura cíclica. Por ejemplo, si un grafo cúbico contiene un triángulo, una transformación Δ-Y reemplazará el triángulo por un solo vértice; cualquier doble cobertura cíclica del grafo más pequeño puede extenderse de nuevo a una doble cobertura cíclica del grafo cúbico original. Por lo tanto, un contraejemplo mínimo a la conjetura de la doble cobertura cíclica debe ser un grafo libre de triángulos , descartando algunos casos como el grafo de Tietze que contienen triángulos. Mediante búsquedas computacionales, se sabe que todo ciclo de longitud 11 o menos en un grafo cúbico forma una configuración reducible, y por lo tanto que cualquier contraejemplo mínimo a la conjetura de la doble cobertura cíclica debe tener una circunferencia de al menos 12. ^{[ 10 ]}

Desafortunadamente, no es posible demostrar la conjetura de la doble cobertura cíclica utilizando un conjunto finito de configuraciones reducibles. Cada configuración reducible contiene un ciclo, por lo que para cada conjunto finito S de configuraciones reducibles existe un número γ tal que todas las configuraciones en el conjunto contienen un ciclo de longitud como máximo γ. Sin embargo, existen snarks con circunferencia arbitrariamente alta, es decir, con límites arbitrariamente altos en la longitud de su ciclo más corto. ^{[ 11 ]} Un snark G con circunferencia mayor que γ no puede contener ninguna de las configuraciones en el conjunto S , por lo que las reducciones en S no son lo suficientemente fuertes como para descartar la posibilidad de que G pueda ser un contraejemplo mínimo.

Si un grafo tiene una doble cubierta cíclica, los ciclos de la cubierta se pueden usar para formar las 2-celdas de una incrustación del grafo en un complejo celular bidimensional . En el caso de un grafo cúbico, este complejo siempre forma una variedad . Se dice que el grafo está incrustado circularmente en la variedad, ya que cada cara de la incrustación es un ciclo simple en el grafo. Sin embargo, una doble cubierta cíclica de un grafo con grado mayor que tres puede no corresponder a una incrustación en una variedad: el complejo celular formado por los ciclos de la cubierta puede tener una topología no manifold en sus vértices. La conjetura de incrustación circular o conjetura de incrustación fuerte ^{[ 9 ]} afirma que todo grafo 2-conexo por vértices tiene una incrustación circular en una variedad. Si es así, el grafo también tiene una doble cubierta cíclica, formada por las caras de la incrustación.

Para grafos cúbicos, la conectividad de 2 vértices y la ausencia de puentes son equivalentes. Por lo tanto, la conjetura de incrustación circular es claramente al menos tan fuerte como la conjetura de doble recubrimiento cíclico. ^{[ 9 ]}

Si existe una incrustación circular, podría no estar en una superficie de género mínimo: Nguyen Huy Xuong describió un grafo toroidal con 2 vértices conectados cuyas incrustaciones circulares no se encuentran en un toro. ^{[ 9 ]}

Una versión más fuerte de la conjetura de incrustación circular que también se ha considerado es la conjetura de que todo grafo 2-conexo por vértices tiene una incrustación circular en una variedad orientable . En términos de la conjetura de doble recubrimiento cíclico, esto es equivalente a la conjetura de que existe un doble recubrimiento cíclico, y una orientación para cada uno de los ciclos en el recubrimiento, tal que para cada arista e los dos ciclos que cubren e están orientados en direcciones opuestas a través de e . ^{[ 9 ]}

Alternativamente, también se han considerado fortalecimientos de la conjetura que involucran coloraciones de los ciclos en la cubierta. El más fuerte de estos es una conjetura de que todo grafo sin puentes tiene una incrustación circular en una variedad orientable en la que las caras pueden ser 5-coloreadas. De ser cierto, esto implicaría una conjetura de WT Tutte de que todo grafo sin puentes tiene un 5-flujo sin cero en ninguna parte . ^{[ 9 ]}

Un tipo de incrustación más fuerte que una incrustación circular es una incrustación poliédrica , una incrustación de un grafo en una superficie de tal manera que cada cara es un ciclo simple y cada par de caras que se intersecan lo hacen en un solo vértice o una sola arista. (En el caso de un grafo cúbico, esto se puede simplificar a un requisito de que cada par de caras que se intersecan lo hagan en una sola arista). Por lo tanto, en vista de la reducción de la conjetura de la doble cobertura cíclica a los snarks, es interesante investigar las incrustaciones poliédricas de los snarks. Incapaz de encontrar tales incrustaciones, Branko Grünbaum conjeturó que no existen, pero Kochol ( 2009a , 2009b ) refutó la conjetura de Grünbaum al encontrar un snark con una incrustación poliédrica. 

• Conjetura de coloración de Petersen

• Fleischner, Herbert (1976), "Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen", Monatshefte für Mathematik , 81 (4): 267– 278, doi : 10.1007/BF01387754 (inactivo el 30 de enero de 2026), S2CID 118767538 {{citation}}: CS1 maint: DOI inactivo desde enero de 2026 ( enlace ) .
• Itai, A.; Rodeh, M. (1978), "Covering a graph by circuits", Automata, Languages ​​and Programming. ICALP 1978. , Lecture Notes in Computer Science (Ausiello, G., Böhm, C. (eds)), vol.  62, Springer, pp. 289– 299, doi : 10.1007/3-540-08860-1_21 , ISBN  978-3-540-08860-8.
• Huck, A. (2000), "Configuraciones reducibles para la conjetura de la doble cobertura cíclica", Matemáticas Aplicadas Discretas , 99 ( 1–3 ): 71–90 , doi : 10.1016/S0166-218X(99)00126-2.
• Jaeger, F. (1985), "Un estudio de la conjetura de la doble cobertura cíclica", Annals of Discrete Mathematics 27 – Cycles in Graphs , North-Holland Mathematics Studies, vol.  27, pp. 1–12 , doi : 10.1016/S0304-0208(08)72993-1 , ISBN  978-0-444-87803-8.
• Kochol, Martin (1996), "Snarks sin ciclos pequeños", Journal of Combinatorial Theory, Serie B , 67 (1) (1.ª  ed.): 34–47 , doi : 10.1006/jctb.1996.0032.
• Kochol, Martin (2009a), "Grafos 3-regulares no 3-coloreables por aristas con incrustaciones poliédricas en superficies orientables", Graph Drawing 2008, Editores: IG Tollis, M. Patrignani , Lecture Notes in Computer Science, vol.  5417, pp . 319–323 .
• Kochol, Martin (2009b), "Incrustaciones poliédricas de snarks en superficies orientables", Actas de la Sociedad Matemática Americana , 137 (5) (5.ª  ed.): 1613–1619 , doi : 10.1090/S0002-9939-08-09698-6.
• Seymour, PD (1979), "Sumas de circuitos", en Bondy, JA; Murty, USR (eds.), Teoría de grafos y temas relacionados , Nueva York: Academic Press, pp. 342–355 , ISBN  978-0121143503.
• Szekeres, G. (1973), "Descomposición poliédrica de grafos cúbicos", Boletín de la Sociedad Matemática Australiana , 8 (3): 367– 387, doi : 10.1017/S0004972700042660.
• Tutte, WT (1987), Correspondencia personal con H. Fleischner (22 de julio de 1987).
• Zhang, Cun-Quan (1997), Flujos enteros y recubrimientos cíclicos de grafos , CRC Press, ISBN 978-0-8247-9790-4.
• Zhang, Cun-Quan (2012), Circuit Double Cover of Graphs , Cambridge University Press, doi : 10.1017/CBO9780511863158 , ISBN 978-0-5212-8235-2.

• Conjetura de doble recubrimiento cíclico , conjetura de incrustación circular y conjetura de Grünbaum , del Open Problem Garden.
• La conjetura de la doble portada del ciclo archivada el 5 de diciembre de 2008 en la Wayback Machine , Dan Archdeacon .
• Weisstein, Eric W. , "Conjetura de la doble cobertura cíclica" , MathWorld