The strong 5-cycle double cover conjecture: every circuit of a bridgeless cubic graph is contained in a 5-cycle double cover

Hoffmann-Ostenhof (2013) conjectured that for every circuit $C$ of every bridgeless cubic graph $G$ there is a cycle double cover of $G$ with at most five 2-regular elements, one of which contains $C$ as a subgraph. This strong 5-cycle double cover conjecture simultaneously implies the strong cycle double cover conjecture (Goddyn) and the 5-cycle double cover conjecture (Celmins, Preissmann), both open since the early 1980s. The source paper proves an equivalent certificate: a 2-regular subgraph $C_0$ of a cubic graph $G$ lies in a 5-cycle double cover if and only if $G$ contains two 2-regular subgraphs $C_1 \supseteq C_0$ and $C_2$ whose edge intersection is a matching $M$ such that $G-M$ admits a nowhere-zero 4-flow. The conjecture is computer-verified for all snarks on at most 34 vertices and for cyclically 5-edge-connected snarks on 36 vertices, partial results cover structured classes, and the July 2026 announced proof of the plain cycle double cover conjecture does not address bounded-size or prescribed-circuit versions. The strong 5-cycle double cover conjecture remains open.

Background

A cycle double cover (CDC) of a graph $G$ is a collection of cycles — subgraphs in which every vertex has even degree — such that every edge of $G$ lies in exactly two members of the collection. (The name comes from the surface-embedding picture: if $G$ embeds in a surface so that every edge borders two distinct faces, the face boundaries form a CDC.) In a cubic graph, i.e. a graph in which every vertex has degree 3, the members of a CDC are 2-regular subgraphs (subgraphs in which every vertex has degree 0 or 2). A graph is bridgeless if deleting no single edge disconnects it; bridges (cut-edges) lie on no cycle, so bridgeless is the natural domain. The cycle double cover conjecture, posed independently in the 1970s by Tutte, Itai and Rodeh, Szekeres, and Seymour, asserts that every bridgeless graph has a CDC. It is standard that it suffices to prove it for snarks: bridgeless cubic graphs of girth at least 5 (girth is the length of a shortest circuit) that admit no proper 3-edge-coloring (an assignment of three colors to the edges such that the three edges at every vertex receive distinct colors); the Petersen graph is the smallest snark.

A nowhere-zero 4-flow on a graph is an assignment of nonzero integers with absolute value less than 4 to the edges of an orientation of the graph so that, at every vertex, the total flow entering equals the total flow leaving. Flows govern small covers: by a theorem of Huck and Kochol, a subdivision of a cubic graph (a graph obtained from it by replacing edges with internally disjoint paths) has a CDC with four elements (a 4-CDC) if and only if it has a nowhere-zero 4-flow, and in that case every 2-regular subgraph of it is a member of some 4-CDC. Since every 3-edge-colorable cubic graph has a nowhere-zero 4-flow, all colourable cubic graphs admit 4-CDCs; the difficulty is concentrated on snarks.

Two classical strengthenings of the CDC conjecture restrict the cover rather than the graph. The 5-cycle double cover conjecture (5-CDCC), formulated in the Ph.D. theses of Celmins and of Preissmann in the early 1980s, states that every bridgeless cubic graph has a CDC with at most five elements; five is best possible, since the Petersen graph has no 4-CDC. The strong cycle double cover conjecture (strong-CDCC), from Goddyn's 1988 thesis, states that for every circuit $C$ of a bridgeless cubic graph — a circuit being a 2-regular and 2-connected subgraph, i.e. a single closed path — some CDC of $G$ contains $C$ as a subgraph of one of its elements. The strong version cannot be extended from circuits to arbitrary 2-regular subgraphs: infinitely many snarks contain 2-factors (spanning 2-regular subgraphs) that lie in no CDC at all, as follows from the infinite family of permutation snarks (snarks containing a 2-factor of exactly two induced circuits) constructed by Hägglund and Hoffmann-Ostenhof, together with the computer-generated examples of Brinkmann et al.

Hoffmann-Ostenhof's note combines the two strengthenings and provides a workable criterion. His Theorem 0.4 states that a cubic graph $G$ has a 5-CDC containing a given 2-regular subgraph $C_0$ if and only if $G$ contains a matching $M$ (a set of edges no two of which share an endpoint) such that $G-M$ has a nowhere-zero 4-flow and $G$ contains two 2-regular subgraphs $C_1 \supseteq C_0$ and $C_2$ with $E(C_1) \cap E(C_2) = M$. He then poses the strong 5-cycle double cover conjecture below, and verifies as a warm-up that every circuit of the Petersen graph is contained in a 5-CDC.

Problem Statement

The strong 5-cycle double cover conjecture (Hoffmann-Ostenhof, 2013): for every circuit $C$ of every bridgeless cubic graph $G$, there exists a cycle double cover $S$ of $G$ with $|S| \le 5$ (a 5-CDC; empty 2-regular subgraphs count as elements, so 'at most five' and 'exactly five' are equivalent) such that $C$ is a subgraph of one of the 2-regular subgraphs belonging to $S$. Equivalently, by the criterion proved in the source paper, the conjecture asks: for every circuit $C$ of every bridgeless cubic graph $G$, do there exist a matching $M \subseteq E(G)$ and two 2-regular subgraphs $C_1, C_2$ of $G$ such that $C \subseteq C_1$, $E(C_1) \cap E(C_2) = M$, and $G - M$ admits a nowhere-zero 4-flow? The problem calls for a proof or a refutation of this universal statement. An affirmative answer would simultaneously resolve the 5-cycle double cover conjecture and the strong cycle double cover conjecture for cubic graphs; a refutation would be a bridgeless cubic graph together with a circuit contained in no 5-CDC. The completion boundary is the general statement: resolving special classes — snarks of bounded order, graphs with tree-and-cycle decompositions, non-separating circuits, 3-edge-colorable graphs — is genuine progress but does not by itself complete the problem.

References

1. Arthur Hoffmann-Ostenhof, A Note on 5-Cycle Double Covers, Graphs and Combinatorics 29 (2013) 977–979, DOI: 10.1007/s00373-012-1169-8, https://doi.org/10.1007/s00373-012-1169-8 (preprint: arXiv:1209.0096, https://arxiv.org/abs/1209.0096)
2. Gunnar Brinkmann, Jan Goedgebeur, Jonas Hägglund, Klas Markström, Generation and properties of snarks, Journal of Combinatorial Theory, Series B 103 (2013) 468–488, DOI: 10.1016/j.jctb.2013.05.001, https://doi.org/10.1016/j.jctb.2013.05.001 (preprint: arXiv:1206.6690, https://arxiv.org/abs/1206.6690)
3. Rui Xu, Strong 5-Cycle Double Covers of Graphs, Graphs and Combinatorics 30 (2014) 495–499, DOI: 10.1007/s00373-012-1266-8, https://doi.org/10.1007/s00373-012-1266-8
4. Arthur Hoffmann-Ostenhof, Cun-Quan Zhang, Zhang Zhang, Cycle double covers and non-separating cycles, European Journal of Combinatorics 81 (2019) 276–284, DOI: 10.1016/j.ejc.2019.06.006, https://doi.org/10.1016/j.ejc.2019.06.006 (preprint: arXiv:1711.10614, https://arxiv.org/abs/1711.10614)
5. Radek Hušek, Robert Šámal, Exponentially Many Circuit Double Covers, preprint (2026), arXiv:2607.24724, https://arxiv.org/abs/2607.24724
6. OpenAI, A proof of the cycle double cover conjecture, technical note, July 9, 2026, https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf (accompanied by a Lean formalization; not yet refereed)
7. Jonas Hägglund, Arthur Hoffmann-Ostenhof, Construction of permutation snarks, Journal of Combinatorial Theory, Series B 122 (2017) 55–67, DOI: 10.1016/j.jctb.2016.05.003, https://doi.org/10.1016/j.jctb.2016.05.003
8. Uldis A. Celmins, On cubic graphs that do not have an edge-3-coloring, Ph.D. thesis, University of Waterloo, 1984
9. Myriam Preissmann, Sur les colorations des arêtes des graphes cubiques, Thèse de Doctorat, Grenoble, 1981
10. L. Goddyn, Cycle covers of graphs, Ph.D. thesis, University of Waterloo, 1988
11. A. Huck, M. Kochol, Five Cycle Double Covers of Some Cubic Graphs, Journal of Combinatorial Theory, Series B 64 (1995) 119–125, DOI: 10.1006/jctb.1995.1029, https://doi.org/10.1006/jctb.1995.1029
12. Herbert Fleischner, Roland Häggkvist, Cycle Double Covers in Cubic Graphs having Special Structures, Journal of Graph Theory 77 (2014) 158–170, DOI: 10.1002/jgt.21779, https://doi.org/10.1002/jgt.21779
13. Xiaofeng Wang, Rui Xu, Dong Ye, Cycle double covers and long circuits of graphs, Journal of Combinatorics 8 (2017) 341–347, DOI: 10.4310/JOC.2017.V8.N2.A6, https://doi.org/10.4310/JOC.2017.V8.N2.A6