Math 2.0

Combinatorics Probabilistic and discrete-geometric methods Conjecture

Cycle double cover conjecture

Builds on GraphCycleBridge

Statement

Let GG be a finite graph, possibly with multiple edges, that has no bridge. The conjecture: there is a finite list of cycles of GG such that each edge of GG lies in exactly two cycles of the list. The list may contain a cycle more than once. Such a list is called a cycle double cover of GG.

Remarks

The conjecture is open. It was posed by Szekeres and, independently, by Seymour. The hypothesis is necessary: a bridge lies on no cycle, so a graph with a bridge has no cycle double cover. For a bridgeless planar graph, each face boundary of a plane embedding splits into edge-disjoint cycles, and each edge lies on exactly two faces. So these cycles form a cycle double cover. The general case reduces to cubic bridgeless graphs, and further to snarks, the cubic bridgeless graphs with no proper edge colouring with 33 colours. If a cubic graph has a proper edge colouring with 33 colours, the unions of two colour classes give three families of disjoint cycles, which together cover each edge twice.

Reading path

To understand this page from the ground up, read these 4 pages in order. The foundations come first.

Show the path as a graph
Bridge, concept, no evidence levelBridgeconceptCycle, concept, no evidence levelCycleconceptGraph, concept, no evidence levelGraphconceptCycle double cover conjecture, conjecture, no evidence levelCycle double cover co…conjecture
Each page uses the pages above it. The colour of the bar on a box shows how strong the evidence is, and the box also gives it as text. The list has the same pages.
  • no evidence level
  1. Bridge concept
  2. Cycle concept
  3. Graph concept
  4. Cycle double cover conjecture conjecture

Further reading

  1. Web https://en.wikipedia.org/wiki/Cycle_double_cover
About this page
TagG2RYQMGG1R
URIm2://G2RYQMGG1R
Kindconjecture
WritingW0 stub
MSC05C38, 05C70
StatusThis copy of the site has no build data. Run m2 status G2RYQMGG1R.
AboutCycle
UsesGraph, Cycle, Bridge
Changed2 November 2026

Markdown · JSON · Edit on GitHub

What this page needs for W1

  • an inventory row: the row of the inventory that the node accounts for (0 of 1)
  • a source with a locator (0 of 1)

The writing levels say how complete the text of a page is. They do not measure its truth.

What links here

No page links to this page yet.