Exponentially Many Circuit Double Covers

Abstract

The cycle double cover conjecture of Szekeres and Seymour, the proof of which was recently announced by OpenAI, states that every bridgeless graph has a collection of cycles covering every edge exactly twice. We study the counting version of this statement for cubic graphs, where we count circuit double covers --- collections of circuits (connected 2-regular subgraphs) covering every edge twice. We show that every 2-edge-connected 3-edge-colorable cubic graph on $n$ vertices has at least $2^{n/2-1}$ circuit double covers, matching our previously conjectured general lower bound. For every 3-edge-connected cubic graph with girth at least 16 we show a weaker exponential lower bound on circuit double covers. For both of these results we use the same system of linear equations used by OpenAI in their proof, however, we provide additional combinatorial interpretation. We characterize planarity of a cubic graph by solvability of this system of equations for arbitrary nowhere-zero $\mathbb Z_2^k$-flow. We give a condition on the flow that is equivalent to existence of a 5-cycle double cover.

Disclosure

“low induced by its labels; Theorem 3.16 then gives the parity condition. Theorem 3.4 guarantees the existence of NZ Z32 -flows, but the remaining problem is to choose one with this additional parity property. Acknowledgments We have used GPT 5.6 and Claude Fable for draft versions of the paper. References [Cel] Uldis A. Celmins, On cubic graphs that do not have an edge 3-coloring, Ph.D. thesis, University of Waterloo, 1984. [DLMS] M. DeVos, R. Langhede, B. Mohar, R.”

PDF page 15

Classification

Drafting limited passages

Multiplier

5

Verified

2026-08-23T19:09:54.462049Z

Structural counts