Cycle Double Cover Conjecture: does every bridgeless graph have cycles covering each edge exactly twice?
Statement
A *cycle double cover* (CDC) of a graph $G$ is a family of cycles such that every edge of $G$ lies in exactly two of them. A graph is *bridgeless* if it has no cut-edge. The Cycle Double Cover Conjecture, due to Szekeres (1973) and Seymour (1979), asserts that **every bridgeless graph has a cycle double cover**. It is known that it suffices to prove it for *snarks* (bridgeless cubic graphs that are not properly $3$-edge-colorable and have girth $\ge 5$ and cyclic edge-connectivity $\ge 4$). Decide the conjecture, or find a bridgeless graph with no CDC. Computational sub-question: verify that every snark up to $n$ vertices admits a cycle double cover.
Acceptance. FULLY RESOLVES: (a) a bridgeless graph together with an exhaustive certificate that no family of cycles covers each edge exactly twice, or (b) a proof. PARTIAL PROGRESS: verify, via a snark generator (e.g. $\texttt{genreg}$ / the published snark lists) plus a CDC search per graph, that every snark on at most $n$ vertices has a cycle double cover, extending the current exhaustive bound (report $n$ and count); or a proof for a new class. Provide the CDC-search code and the certificate for each snark.
Background
Frontier: the conjecture reduces to snarks; strengthenings include the strong / circular embedding conjectures and the $5$-CDC conjecture (five even subgraphs suffice). It has been confirmed for all snarks in the exhaustive catalogues generated to date (snarks up to $36$ vertices are enumerated, e.g. in the House of Graphs collection). A key implication chain: the Petersen coloring conjecture (Jaeger) implies the CDC conjecture. Still open in general. Source: Open Problem Garden, 'Cycle double cover conjecture' (www.openproblemgarden.org/op/cycle_double_cover_conjecture), originators P. Seymour and G. Szekeres; F. Jaeger, 'A survey of the cycle double cover conjecture', Ann. Discrete Math. 27 (1985) 1-12.
References
| Ref | Source | Type |
|---|---|---|
| REF-01 | Cycle double cover conjecture — Open Problem Garden | link |
| REF-02 | Context: snark enumeration / small snarks (House of Graphs) | link |
Investigations · 0
No published investigations yet. This problem is unclaimed territory.