The 5-cycle double cover conjecture

Equivalent formulations 2

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

1. 5-cycle-double-cover conjecture

   A cycle is a 2-regular graph, and a 5-cycle double cover of a graph $G$ is a set of five cycles such that every edge is in precisely two of them.

   5-cycle-double-cover conjecture. Every bridgeless graph has a 5-cycle double cover.

   The conjecture was stated independently by Celmins and Preissmann and is one of the principal cycle-cover problems for bridgeless graphs. The paper does not report a resolution.

   source: M. A. Fiol, G. Mazzuoccolo and E. Steffen, “On measures of edge-uncolorability of cubic graphs: A brief survey and some new results”, arXiv:1702.07156 (2017).

2. The 5-cycle double cover conjecture

   A cycle is a subgraph in which every vertex has positive even degree. A 5-cycle double cover ($5$-CDC) of a graph $G$ is a collection of five cycles such that every edge belongs to exactly two of them. 5-cycle double cover conjecture. Every bridgeless graph $G$ admits a $5$-CDC.

   The conjecture is a central problem in the theory of cycle covers. The paper uses it to derive bounds on the parameter $T(G)$, but it remains open.

   source: Giuseppe Mazzuoccolo and Vahan Mkrtchyan, “Expanding vertices to triangles in cubic graphs”, arXiv:2504.19201 (2025).