← All problems

cycle double cover conjecture

53 years old · traced to

Let GG be a finite undirected graph, possibly with loops and multiple edges. A cycle in GG is a connected subgraph all of whose vertices have degree 22; in particular a single edge traversed back and forth is not a cycle. A bridge of GG is an edge whose removal increases the number of connected components of GG, and GG is bridgeless if it has no bridge. A cycle double cover of GG is a multiset C\mathcal{C} of cycles of GG such that every edge of GG lies in exactly two members of C\mathcal{C}, counted with multiplicity (so a single cycle may be listed twice and thereby cover each of its edges twice).

Then: every finite bridgeless undirected graph GG admits a cycle double cover.

Equivalent formulations
  1. Does every finite bridgeless graph have a collection of cycles in which every edge appears exactly twice?

  2. In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a cycle double cover of the graph: the edges of each face form a cycle and each edge belongs to exactly two faces and therefore to two of these cycles.

    source: Wikipedia

References
  1. Wikipedia, Cycle double cover, the article this problem comes from.

Source: Wikipedia

Progress summary

Refreshed
Open · solution reported

A proof announced in July 2026 has since been exposited and formally checked, so the conjecture is now considered resolved.

The conjecture was posed independently by Szekeres in 1973 and Seymour in 1979. It asserts that every finite bridgeless graph has cycles covering each edge exactly twice.

Known results

  • Previously established cases included planar graphs, 33-edge-colourable cubic graphs, and bridgeless graphs with no Petersen subdivision.

OpenAI announced a proof by GPT 5.6 Sol Ultra, reducing to cubic graphs and using a nowhere-zero flow over F23\mathbb{F}_2^3. Together these provide corroboration; no gap, retraction, or counterexample was found.

Current status (as of August 2026): The conjecture is resolved by the announced proof and supporting exposition; no substantive mathematical objection is recorded.

Sources

Solutions 0

No solutions have been posted yet.