**The Cycle Double Cover
Conjecture **

A *cycle* in a graph is a simple closed walk. The following Double
Cover Conjecture is one of the most famous problems in graph theory. It is due
independently to Szekeres [Sz]
and Seymour [Se].

**Conjecture:** *Every bridgeless graph has a collection of cycles
which together contain every edge exactly twice.*

The conjecture is almost easy. Form *G_2* from *G* by replacing
each edge with two parallel edges. Then *G_2* has every vertex of even
degree. It follows easily from induction that *G_2* has an edge partition
into cycles. However, some of these cycles may be of length two and hence do
not correspond to cycles in a double cover of *G*.

A stumbling block to inductive proofs has been found in many different
contexts. Namely, suppose that each edge *e* is assigned a weight *w(**e)* = 1 or 2 so that at each vertex the sum
of the weights is even. Can we find a cycle cover so that each edge *e* is
used *w(**e)* times? No. A counterexample is
formed from the Petersen graph (of course) by assigning weights 2 on a perfect
matching and weights 1 on two disjoint 5-cycles.

There are several variations of a topological nature. For example there is the Circular Embedding Conjecture.

**Conjecture:** *Every 2-connected graph has an embedding in some
surface such that each face is bounded by a simple cycle.*

The face boundaries form a cycle double cover. The two conjectures are equivalent for cubic graphs, but the second is stronger for noncubic graphs. An even stronger conjecture asserts that the faces of the circular embedding can be properly 5-colored. Likewise one could require the embedding to be in an orientable surface.

A stronger conjecture due to Goddyn [G] allows you to fix one cycle in the cover.

**Conjecture:** *For every bridgeless* G *and
every cycle* C *of* G, *there is a cycle double cover of* G *containing* C.

Partial results are too numerous to mention here. I refer the interested reader to the survey article by Jaeger [J].

A dual form of the problem is called "Fulkerson's Conjecture".

**References:**

[G] L. Goddyn,
“Cycle covers of graphs”, Ph.D. Thesis,

[J] F. Jaeger, A survey of the cycle double cover
conjecture, in: Cycles in Graphs (B. Alspach and
CC.D. Alspach Eds.) Vol **27** *Annals of Discrete
Math.*

[Se] P.D. Seymour, Sums of circuits, in: Graph Theory and Related Topics, (J.A. Bondy and U.R.S. Murty Eds.) Academic Press (1979) 341-355

[Sz] G. Szekeres,
Polyhedral decompositions of cubic graphs, *Bull. Austral.
Math. Soc.* **8** (1973) 367-387.

Submitted by: Dan Archdeacon, Department of Mathematics
and Statistics,

Send comments to *dan.archdeacon@uvm.edu
*

August, 1995