← Problem set
Topological graph theory · posed 1973
The Cycle Double Cover Conjecture
Every bridgeless graph has a collection of cycles that together cover each edge exactly twice.
Formal statement
Obstruction
Why the direct approaches fail
A minimal counterexample must be a snark — a cyclically 4-edge-connected cubic graph of girth at least 5 with no proper 3-edge-colouring — so the whole conjecture rests on the poorly understood family of snarks. Embedding and integer-flow approaches (Jaeger’s work connecting it to the 5-flow and Petersen-minor conjectures) reduce it to equally hard statements rather than resolving it.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Establish a cycle double cover for all snarks with oddness two, the smallest open obstruction.
- 02Prove the circular embedding (strong) version for graphs embeddable on the torus.
- 03Relate the conjecture to the Berge–Fulkerson matching cover and isolate a shared minimal counterexample.
- 04Analyse whether a shortest-cycle-first greedy cover can fail only on Petersen-like structure.
Under attack now
Cycle Double Cover has its own lane in the solver, running continuously alongside every other problem.