Cycle Double Cover Conjecture (1978/1979)

Originator(s): George Szekeres (1973) and Paul Seymour (1979, Princeton University), independently

Conjecture/Question: Every graph without cut-edges admits a list of cycles that together cover each edge exactly twice.

Definitions/Background/motivation: In the original formulation, "cycle" is used to mean "even graph", but these phrasings are equivalent since every even graph decomposes into cycles. The earliest statement of the problem seems to be in Szekeres [S] (thanks to Alejandro Erickson for the reference). The conjecture is implied by the Strong Embedding Conjecture.

Comments/Partial results: Goddyn [G] proved that a smallest counterexample must be a snark with girth at least 8. Alspach-Goddyn-Zhang [AGZ] proved that the conjecture holds for every graph containing no subdivision of the Petersen graph. Jaeger [J] provides a survey.

References:
[AGZ] Alspach, Brian; Goddyn, Luis; Zhang, Cun Quan. Graphs with the circuit cover property. Trans. Amer. Math. Soc. 344 (1994), no. 1, 131--154.
[G] Goddyn, Luis. A girth requirement for the double cycle cover conjecture. Cycles in graphs (Burnaby, B.C., 1982), 13--26, North-Holland Math. Stud., 115, North-Holland, Amsterdam, 1985.
[J] Jaeger, Francois. A survey of the cycle double cover conjecture. Cycles in graphs (Burnaby, B.C., 1982), 1--12, North-Holland Math. Stud., 115, North-Holland, Amsterdam, 1985.
[S] Szekeres, G. Polyhedral decompositions of cubic graphs. Bull. Austral. Math. Soc. 8 (1973), 367--387.

Keywords:

Back to Index Page Link to Glossary