The cycle double cover conjecture for bridgeless graphs

Let Γ\Gamma be a graph. A cycle double cover is a collection of cycles such that every edge of Γ\Gamma lies in exactly two cycles. For a cubic graph, this is equivalent to requiring that exactly three cycles pass through each node. A simplicial surface has Γ\Gamma as its face graph when its faces correspond to the vertices and edges of Γ\Gamma in the usual incidence structure.

Cycle double cover conjecture. Every cubic graph containing no bridges has a cycle double cover, or equivalently is the face graph of a simplicial surface. More generally, every bridgeless graph admits a cycle double cover.

The conjecture would characterize which bridgeless cubic graphs arise as face graphs of simplicial surfaces and remains open: it is not known whether all cubic bridgeless graphs admit a cycle double cover.

Equivalent formulations 1

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

  1. The cycle double cover conjecture for bridgeless graphs

    A graph is bridgeless if it has no bridges, meaning no edge whose deletion increases the number of connected components. A cycle double cover is a family of cycles such that every edge of the graph belongs to exactly two members of the family.

    Cycle double cover conjecture. Every bridgeless graph has a cycle double cover.

    This is a major open problem in graph theory. The conjecture is known in several special cases, but remains unresolved for general bridgeless graphs.

    source: Delio Mugnolo and Marvin Plümer, “Lower Estimates on Eigenvalues of Quantum Graphs”, arXiv:1907.13350 (2020).

Sources & referencesView supporting material

Primary source

Reymond Akpanya and Tom Goertzen, “Surfaces with given Automorphism Group”, arXiv:2307.12681 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.