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, University of Waterloo, Waterloo, Ontario, Canada.

[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. North Holland (1985) 1-12,

[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, University of Vermont, Burlington VT 05405 USA.

Send comments to dan.archdeacon@uvm.edu

August, 1995