The cycle double cover conjecture — every bridgeless graph admits a collection of cycles covering each edge exactly twice — was settled affirmatively by a proof announced in July 2026, but existence says nothing about how many covers there are. This record states the counting problem posed by Hušek and Šámal: prove or refute that every 2-connected cubic graph on n vertices (for cubic graphs, 2-connected is the same as connected and bridgeless) has at least 2n/2−12^{n/2-1} circuit double covers, where a circuit double cover is a family of circuits (connected 2-regular subgraphs) covering every edge exactly twice. The bound is tight for the Klee graphs and has recently been proven for 3-edge-colorable cubic graphs; it remains open for snarks — bridgeless cubic graphs with no 3-edge-coloring — of arbitrary girth, where even an exponential lower bound with any fixed positive exponent is known only under additional hypotheses (3-connectivity and girth at least 16).

Background

A cubic graph is a graph in which every vertex has exactly three incident edges. A bridge is an edge whose deletion disconnects the graph; a graph with no bridge is called bridgeless. For connected cubic graphs, being bridgeless coincides with being 2-connected (having no cut vertex), because vertex-connectivity and edge-connectivity agree for cubic graphs. A cycle double cover (CyDC) of a graph is a collection of cycles — subgraphs in which every vertex has even degree — such that every edge lies in exactly two members of the collection. The classical cycle double cover conjecture, posed in the 1970s, asserts that every bridgeless graph has a CyDC; a proof for all bridgeless graphs was announced by OpenAI in July 2026 together with a Lean formalization, and an exposition was posted on arXiv by Sang-il Oum. This settles existence, but not abundance.

For counting, the natural unit is a circuit: a connected 2-regular subgraph, i.e., a single closed cycle in the everyday sense of the word. A circuit double cover (CiDC) is a family of circuits covering every edge exactly twice; in a cubic graph the same circuit never needs to appear twice, so the family is effectively a set. Every CiDC is a CyDC, and every CyDC can be decomposed into circuits, so the two notions agree on existence — but not on counting. Counting CiDCs is also the geometrically meaningful count: the circuits of a CiDC are exactly the face boundaries of a strong embedding (an embedding on a closed surface in which every face boundary is a circuit) of the graph, so counting CiDCs amounts to counting face-double-covering embeddings.

Hušek and Šámal initiated this counting problem in 'Counting circuit double covers' (preprint 2023, journal version 2025). They conjectured that every bridgeless cubic graph on n vertices has at least 2n/2−12^{n/2-1} CiDCs, and they proved the bound best possible: the Klee graphs — the cubic graphs obtained from three parallel edges by repeatedly replacing vertices by triangles, equivalently the uniquely 3-edge-colorable planar cubic graphs — have exactly 2n/2−12^{n/2-1} CiDCs. They proved exponential lower bounds for planar graphs and almost-exponential bounds for graphs embedded on a fixed surface with representativity at least 4 (representativity is the minimum number of points at which any noncontractible closed curve on the surface meets the embedded graph), showed that the number of CiDCs multiplies over small edge-cuts (which forces a smallest counterexample to have no 2-edge-cut, no nontrivial 3-edge-cut, and no triangle or 4-cycle), and verified the conjecture computationally on all biconnected cubic graphs up to 20 vertices without short cycles, with the Petersen graph coming closest at a factor of about 3.25 above the bound.

Their 2026 follow-up 'Exponentially Many Circuit Double Covers' attacks the conjecture with the machinery of the announced CDC proof. The key tool is the nowhere-zero Z2kZ_2^k-flow: an assignment of a nonzero vector of the k-dimensional vector space over the two-element field to each edge such that the three vectors at every vertex of a cubic graph sum to zero. A cubic graph admits such a flow with k = 2 exactly when it is 3-edge-colorable (that is, its edges can be colored with three colors so that the three edges at every vertex carry three distinct colors; the three nonzero vectors play the role of the three colors), and a classical theorem guarantees one with k = 3 for every bridgeless cubic graph. Bridgeless cubic graphs that are not 3-edge-colorable are called snarks; the Petersen graph is the smallest. The reformulated OpenAI argument shows that, for a fixed nowhere-zero Z2kZ_2^k-flow, a certain system of linear equations over the two-element field (one equation per edge, plus auxiliary per-vertex variables) has solutions corresponding bijectively to labeled 2k2^k-cycle double covers, and that for k = 3 the system is always solvable. Counting solutions, and then bounding how many labeled covers can induce the same CiDC, yields lower bounds on the number of CiDCs.

With this machinery the 2026 paper proves two partial results: every 2-connected 3-edge-colorable cubic graph on n vertices has at least 2n/2−12^{n/2-1} CiDCs (Theorem 1.7, matching the conjectured bound), and every 3-connected cubic graph with girth — the length of a shortest cycle — at least 16 has 2Ω(n)2^{\Omega(n)} CiDCs (Theorem 1.8). The latter relies on a 2020 unrefereed preprint theorem of DeVos, Langhede, Mohar and Šámal that every 3-connected cubic graph has at least 2n/2−12^{n/2-1} nowhere-zero Z23Z_2^3-flows. The main conjecture — the exact bound for graphs that are not 3-edge-colorable, of arbitrary girth — remains open.

Problem Statement

Prove or refute the counting circuit double cover conjecture of Hušek and Šámal (Conjecture 5 of 'Counting circuit double covers', 2023/journal 2025; restated as Conjecture 1.5 of 'Exponentially Many Circuit Double Covers', 2026). Write ν(G)\nu(G) for the number of circuit double covers of GG, where a circuit double cover is an unordered family of circuits (connected 2-regular subgraphs) of GG such that every edge belongs to exactly two members of the family, and no circuit is counted twice (in a cubic graph no circuit ever needs to repeat). The conjecture asserts that

ν(G)≥2n/2−1\nu(G) \ge 2^{n/2-1}

for every 2-connected cubic graph GG on nn vertices. For connected cubic graphs, 2-connected is equivalent to bridgeless (having no bridge), so the conjecture can be stated equally for all connected bridgeless cubic graphs; both source papers work with connected graphs, and connectedness is genuinely required — the count multiplies over components, so a disjoint union of two copies of K4K_4 (each with ν=2\nu = 2) already falls below the bound 28/2−1=82^{8/2-1} = 8.

The 3-edge-colorable case is already proven affirmatively; the conjecture's remaining open cases are the graphs that are not 3-edge-colorable (snarks), and the known exponential results for snarks require 3-connectivity and girth at least 16, so these cases include snarks of small girth such as the Petersen graph and its expansions. The bound cannot be strengthened in general: the Klee graphs attain exactly 2n/2−12^{n/2-1} circuit double covers. The weaker assertion that every 2-connected cubic graph has at least 2cn2^{cn} circuit double covers for some constant c>0c > 0 does not by itself answer the conjecture as stated.

References

  1. Radek Hušek, Robert Šámal: Exponentially Many Circuit Double Covers (2026), arXiv:2607.24724, doi:10.48550/arXiv.2607.24724, https://arxiv.org/abs/2607.24724
  2. Radek Hušek, Robert Šámal: Counting circuit double covers, Journal of Graph Theory 108 (2025), 374–395, doi:10.1002/jgt.23187; preprint arXiv:2303.10615 (2023), doi:10.48550/arXiv.2303.10615, https://arxiv.org/abs/2303.10615
  3. Matt DeVos, Rikke Langhede, Bojan Mohar, Robert Šámal: Many flows in the group connectivity setting (2020), arXiv:2005.09767, doi:10.48550/arXiv.2005.09767, https://arxiv.org/abs/2005.09767
  4. Jorik Jooken, Ben Seamone, Carol T. Zamfirescu: Counting Small Cycle Double Covers (2025), arXiv:2506.10604, doi:10.48550/arXiv.2506.10604, https://arxiv.org/abs/2506.10604
  5. Meike Weiß, Reymond Akpanya, Alice C. Niemeyer: On 3-Connected Planar Graphs with Unique Orientable Circuit Double Covers (2026), arXiv:2601.10171, doi:10.48550/arXiv.2601.10171, https://arxiv.org/abs/2601.10171
  6. OpenAI: A Proof of the Cycle Double Cover Conjecture (July 9, 2026), https://cdn.openai.com/pdf/04d1d1e4-bc75-476a-97cf-49055cd98d31/cdc_proof.pdf
  7. OpenAI: CDC Lean formalization (2026), GitHub repository, https://github.com/openai/cdc-lean
  8. Sang-il Oum: A proof of the cycle double cover conjecture by OpenAI: An exposition (2026), arXiv:2607.16356, doi:10.48550/arXiv.2607.16356, https://arxiv.org/abs/2607.16356
  9. Giuseppe Mazzuoccolo, Vahan Mkrtchyan: Expanding vertices to triangles in cubic graphs (2025), arXiv:2504.19201, doi:10.48550/arXiv.2504.19201, https://arxiv.org/abs/2504.19201