The 5-cycle double cover conjecture (Celmins–Preissmann): is the universal cycle double cover number equal to five?

The classical cycle double cover (CDC) conjecture — every bridgeless graph admits a collection of cycles covering each edge exactly twice — was resolved in July 2026 by a proof announced by OpenAI, produced by its model GPT 5.6 and accompanied by a Lean proof-assistant formalization and two independent expositions (as of late August 2026 it had not yet appeared in a refereed journal). The proof moreover yields an 8-cycle double cover (a CDC by at most eight Eulerian subgraphs) for every bridgeless graph. Combined with Jaeger's classical theorem that a loopless cubic graph has a 4-CDC only if it is 3-edge-colorable, and the Petersen graph, the smallest universal constant $k$ for which every bridgeless graph has a $k$-CDC is now known to lie in $\{5,6,7,8\}$. The headline residual conjecture is the 5-cycle double cover conjecture of Celmins (1984) and Preissmann (1981), asserting that five Eulerian subgraphs always suffice. This conjecture is open: the newest primary source (Hušek–Šámal, 27 July 2026) explicitly re-poses it, gives an equivalent nowhere-zero $\mathbb{Z}_2^3$-flow formulation, and states that the new methods are not known to extend to it.

Background

A cycle double cover (CDC) of a graph $G$ is a collection of cycles — equivalently, since every Eulerian subgraph decomposes into edge-disjoint cycles, a collection of Eulerian subgraphs (subgraphs in which every vertex has even degree) — such that every edge of $G$ belongs to exactly two members of the collection. A bridge is an edge whose deletion increases the number of connected components; a bridge lies on no cycle, so only bridgeless graphs can admit a CDC. The CDC conjecture, circulating since the 1970s (Seymour, Szekeres; an equivalent form was stated by Itai and Rodeh), asserted that every bridgeless graph has one. In July 2026, OpenAI announced a proof, produced by the model GPT 5.6 and accompanied by a Lean proof-assistant formalization in the repository openai/cdc-lean; independent expositions by Oum and by Geelen reconstruct the argument. The proof reduces the problem to loopless cubic graphs (graphs in which every vertex has degree three) and uses a nowhere-zero $\mathbb{F}_2^3$-flow (an assignment of a nonzero vector of the three-dimensional vector space over the two-element field to each edge, balancing at every vertex) plus linear algebra; quantitatively it establishes that every bridgeless graph has an 8-cycle double cover (8-CDC): a CDC consisting of at most eight Eulerian subgraphs. A classical theorem of Jaeger states that for a loopless cubic graph, having a 3-CDC, having a 4-CDC, and being 3-edge-colorable are equivalent; since the Petersen graph (the smallest bridgeless cubic graph that is not 3-edge-colorable) therefore has no 4-CDC, the smallest integer $k$ such that every bridgeless graph has a $k$-CDC satisfies $5\le k\le 8$. The 5-cycle double cover conjecture, stated in Myriam Preissmann's 1981 Grenoble thesis and Uldis Celmins's 1984 Waterloo thesis, asserts that $k=5$: every bridgeless graph admits a CDC consisting of at most five Eulerian subgraphs. Two conventions matter for reading the statement. First, the members of the cover are arbitrary even (Eulerian) subgraphs, not necessarily connected circuits — an even subgraph decomposing into several circuits counts as one member, and empty subgraphs are allowed, which is what makes 'at most five' well defined. Second, graphs may have loops and parallel edges; a loop can be handled separately, since inserting a loop into (or deleting it from) any member of a cover changes the degree of its vertex by two and so never affects evenness — a loop must simply appear in exactly two members. The conjecture is usually attacked on cubic graphs, where even subgraphs are 2-regular and a minimal counterexample to CDC-type statements is a snark (a bridgeless cubic graph of chromatic index 4, i.e. not 3-edge-colorable, conventionally also cyclically 4-edge-connected — no set of fewer than four edges separates it into two parts each containing a cycle — and of girth, the length of a shortest cycle, at least 5). Before 2026, all positive results were for special classes: Huck and Kochol (1995) proved that a bridgeless cubic graph with a 2-factor (a spanning subgraph in which every vertex has degree 2, i.e. a disjoint union of cycles covering all vertices) with at most two odd components has a 5-CDC; Hoffmann-Ostenhof (2013) characterized when a 2-factor sits inside a 5-CDC; Liu, Hao, Luo and Zhang (2024) gave a sufficient condition, related to shortest even-subgraph covers, under which a cubic graph of weak oddness at most two (oddness being the minimum number of odd components of a 2-factor) has a 5-CDC, and proved unconditionally that every oddness-2 cubic graph of girth at least 30 has one; and Li, Hao, Luo and Zhang (2025) approached the conjecture through non-separating cycles. The same source section that poses the 5-CDC conjecture records three neighboring open strengthening directions that remain open after the 2026 proof: the orientable 5-CDC conjecture of Archdeacon and Jaeger (a CDC by at most five directed Eulerian subgraphs in which each edge is used once in each direction, which would imply Tutte's 5-flow conjecture on nowhere-zero 5-flows); the Berge–Fulkerson conjecture (every bridgeless cubic graph has six perfect matchings — spanning 1-regular subgraphs — such that every edge is in exactly two of them, equivalently a 6-cycle 4-cover); and the strong embedding conjecture (every 2-connected graph has a 2-cell embedding — an embedding in which every face is homeomorphic to an open disk — on some surface, in which every face boundary is a single cycle). These are logically separate problems, not part of the question posed here.

Problem Statement

Does every finite bridgeless (multi)graph — a graph with no bridge, i.e. no edge whose deletion increases the number of connected components — admit a 5-cycle double cover: a collection of at most five Eulerian subgraphs (subgraphs in which every vertex has even degree) such that every edge of the graph belongs to exactly two of them? Equivalently: letting $k$ denote the smallest integer such that every bridgeless graph has a $k$-cycle double cover (a cover by at most $k$ Eulerian subgraphs), is $k=5$? It is known that $5\le k\le 8$: by a theorem of Jaeger, a loopless cubic graph (one in which every vertex has degree three) has a 4-cycle double cover only if it is 3-edge-colorable, and the Petersen graph — the standard example of a bridgeless cubic graph that is not 3-edge-colorable — therefore has no 4-cycle double cover, while the July 2026 proof of the cycle double cover conjecture yields an 8-cycle double cover for every bridgeless graph. An admissible answer is either (i) a proof that every bridgeless graph has a 5-cycle double cover, or (ii) an explicit bridgeless graph together with a verification that no family of at most five Eulerian subgraphs covers each of its edges exactly twice. The members of the cover are arbitrary even subgraphs (possibly disconnected, possibly empty); loops and parallel edges are permitted in the input graph.

References

1. Sang-il Oum, A proof of the cycle double cover conjecture by OpenAI: An exposition, arXiv:2607.16356 (2026), https://arxiv.org/abs/2607.16356
2. Radek Hušek, Robert Šámal, Exponentially Many Circuit Double Covers, arXiv:2607.24724 (2026), https://arxiv.org/abs/2607.24724
3. Jim Geelen, OpenAI's proof of the Cycle Double Cover Theorem, arXiv:2607.15399 (2026), https://arxiv.org/abs/2607.15399
4. OpenAI, A proof of the cycle double cover conjecture (technical note, July 2026), https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf
5. Uldis Alfred Celmins, On cubic graphs that do not have an edge-3-colouring, Ph.D. thesis, University of Waterloo, 1984 (ProQuest LLC, Ann Arbor, MI, 1985; MR 2634187), https://arxiv.org/abs/2607.16356
6. Myriam Preissmann, Sur les colorations des arêtes des graphes cubiques, Ph.D. thesis, Université de Grenoble, 1981 (no DOI), https://arxiv.org/abs/2607.16356
7. Dan Archdeacon, Face colorings of embedded graphs, Journal of Graph Theory 8 (1984), no. 3, 387–398, doi:10.1002/jgt.3190080307, https://doi.org/10.1002/jgt.3190080307
8. D. R. Fulkerson, Blocking and anti-blocking pairs of polyhedra, Mathematical Programming 1 (1971), 168–194, doi:10.1007/BF01584085, https://doi.org/10.1007/BF01584085
9. Jean-Claude Bermond, Bill Jackson, François Jaeger, Shortest coverings of graphs with cycles, Journal of Combinatorial Theory, Series B 35 (1983), no. 3, 297–308, doi:10.1016/0095-8956(83)90056-4, https://doi.org/10.1016/0095-8956(83)90056-4
10. Genghua Fan, Covering Graphs by Cycles, SIAM Journal on Discrete Mathematics 5 (1992), no. 4, 491–496, doi:10.1137/0405039, https://doi.org/10.1137/0405039
11. A. Huck, M. Kochol, Five Cycle Double Covers of Some Cubic Graphs, Journal of Combinatorial Theory, Series B 64 (1995), no. 1, 119–125, doi:10.1006/jctb.1995.1029, https://doi.org/10.1006/jctb.1995.1029
12. Arthur Hoffmann-Ostenhof, A Note on 5-Cycle Double Covers, Graphs and Combinatorics 29 (2013), no. 4, 977–979, arXiv:1209.0096, doi:10.1007/s00373-012-1169-8, https://arxiv.org/abs/1209.0096
13. Siyan Liu, Rong-Xia Hao, Rong Luo, Cun-Quan Zhang, Five-cycle double cover and shortest cycle cover, Journal of Graph Theory 108 (2024), no. 1, 39–49, doi:10.1002/jgt.23164, https://doi.org/10.1002/jgt.23164
14. Xiaoyu Li, Rong-Xia Hao, Rong Luo, Cun-Quan Zhang, Non-separating cycles and 5-cycle double covers, Discrete Mathematics 348 (2025), no. 9, 114515, doi:10.1016/j.disc.2025.114515, https://doi.org/10.1016/j.disc.2025.114515
15. Melody Chan, A survey of the cycle double cover conjecture (2009), https://www.math.brown.edu/mchan2/cdc.pdf
16. Jorik Jooken, Ben Seamone, Carol T. Zamfirescu, Counting Small Cycle Double Covers, arXiv:2506.10604 (2025), https://arxiv.org/abs/2506.10604
17. Babak Ghanbari, Robert Šámal, Facial diagrams and cycle double cover, arXiv:2605.01410 (2026), https://arxiv.org/abs/2605.01410
18. Meike Weiß, Reymond Akpanya, Alice C. Niemeyer, On 3-Connected Planar Graphs with Unique Orientable Circuit Double Covers, arXiv:2601.10171 (2026), https://arxiv.org/abs/2601.10171
19. Paulo Magalhães Júnior, Antonio Kelson Silva, On some perfect matching conjectures in infinite, cubic, bridgeless graphs, arXiv:2607.29511 (2026), https://arxiv.org/abs/2607.29511