The "cycle double cover conjecture" states that every bridgeless graph contains a set of cycles which cover each edge of

Definitions and mathematical statement

Let $G=(V,E)$ be a finite undirected bridgeless graph: deleting any one edge does not increase the number of connected components. A cycle is a connected $2$-regular subgraph. For a simple graph it has length at least three. The equivalent loopless multigraph formulation permits a two-edge cycle formed by parallel edges.

A cycle double cover is a finite multiset $\mathcal C$ of cycles such that \[ \sum_{C\in\mathcal C}\mathbf 1_{\{e\in E(C)\}}=2 \qquad\text{for every }e\in E. \] Cycle occurrences are counted with multiplicity. The cycle double cover conjecture asserts that every finite bridgeless graph has such a cover.

Repeated cycles are allowed: for example, a graph consisting of one cycle is covered by taking that cycle twice. The cycles may overlap in vertices and edges, but the total use of each edge must be exactly two. Arbitrary fractional weights on cycles would give a different relaxation. A bridge cannot lie on any cycle, so the bridgeless hypothesis is necessary. Disconnected graphs are included, and their components can be treated independently; isolated vertices impose no covering requirement. The problem asks for existence for all graphs, without assuming planarity, regularity, or a particular edge coloring.

Short English statement

Does every finite bridgeless graph admit a multiset of cycles covering every edge exactly twice?

Sources

• S1 ULAM.AI and the UnsolvedMath Contributors, supplied problems.json, record 3100019 (AMR-030-0019), AMR Open Problem Lists. Catalogue identity and source transcription; CC BY 4.0. https://huggingface.co/datasets/ulamai/UnsolvedMath.
• S2 Cooper - Combinatorial Problems I Like (2020 snapshot), Graphs, Hypergraphs, Set Systems, Designs, source-order bullet 19. Original source indexed by AMR-030-0019. https://people.math.sc.edu/cooper/combprob.html.