TOPICS
Search

Cycle Double Cover Conjecture

The cycle double cover conjecture states that every bridgeless graph has a collection of cycles which together contain every edge exactly twice. This conjecture was independently formulated by Szekeres (1973) and Seymour (1979).

In July 2026, OpenAI released a claimed proof described as AI-generated (OpenAI 2026a, Pegg 2026), the prompt it reported led to the proof (OpenAI 2026b), and an accompanying Lean formalization for finite loopless bridgeless multigraphs (OpenAI 2026c). As of July 2026, the claim had not yet appeared in a refereed publication.

A dual form of the problem is called the Fulkerson conjecture.

The now-refuted Petersen coloring conjecture would have implied a strengthening of the cycle double cover conjecture. Its counterexamples do not refute this weaker conjecture.

See also

Bridgeless Graph, Cycle Double Cover, Fulkerson Conjecture, Hamiltonian Graph, Petersen Coloring Conjecture

Explore with Wolfram|Alpha

References

Archdeacon, D. "The Cycle Double Cover Conjecture." http://www.cems.uvm.edu/~archdeac/problems/cyclecov.htm.Goddyn, L. "Cycle Covers of Graphs." PhD thesis. Waterloo, Ontario, Canada: University of Waterloo, 1988.Jaeger, F. "A Survey of the Cycle Double Cover Conjecture." In Cycles in Graphs (Ed. B. Alspach and C. D. Alspach). North Holland, pp. 1-12, 1985.OpenAI. "A Proof of the Cycle Double Cover Conjecture." July 9, 2026a. https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf.OpenAI. "Prompt Used for 'A Proof of the Cycle Double Cover Conjecture'." July 9, 2026b. https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_prompt.pdf.OpenAI. "CDC Lean Formalization." GitHub repository, July 9, 2026c. https://github.com/openai/cdc-lean. Pegg, E. Jr. "Get Snarky: The Cycle Double Cover Conjecture--An AI Proof?" Wolfram Community, July 11, 2026. https://community.wolfram.com/groups/-/m/t/3756327.Seymour, P. D. "Sums of Circuits." In Graph Theory and Related Topics (Ed. J. A. Bondy and U. R. S. Murty). New York: Academic Press, pp. 341-355, 1979.Szekeres, G. "Polyhedral Decompositions of Cubic Graphs." Bull. Austral. Math. Soc. 8, 367-387, 1973.West, D. "Cycle Double Cover Conjecture (1978/1979)." http://www.math.uiuc.edu/~west/openp/cdc.html.

Referenced on Wolfram|Alpha

Cycle Double Cover Conjecture

Cite this as:

Weisstein, Eric W. "Cycle Double Cover Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/CycleDoubleCoverConjecture.html

Subject classifications