Cycle double cover

Unsolved problem in mathematics:
Does every bridgeless graph have a multiset of cycles covering every edge exactly twice?
(more unsolved problems in mathematics)
A cycle double cover of the Petersen graph, corresponding to its embedding on the projective plane as a hemi-dodecahedron.

In graph-theoretic mathematics, a cycle double cover is a collection of cycles in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.

It is an unsolved problem, posed by W. T. Tutte,[1] Itai and Rodeh,[2] George Szekeres[3] and Paul Seymour[4] and known as the cycle double cover conjecture, whether every bridgeless graph has a cycle double cover. The conjecture can equivalently be formulated in terms of graph embeddings, and in that context is also known as the circular embedding conjecture.

  1. ^ Tutte (1987).
  2. ^ Itai & Rodeh (1978).
  3. ^ Szekeres (1973).
  4. ^ Seymour (1979).