Cycle double cover conjecture

Cycle Double Cover Conjecture

For every graph with no bridge, there is a list of cycles so that every edge is contained in exactly two.

The conjecture is proven for the following special cases.

Both the book by Cun-Quan Zhang and the website Openproblemgarden give a proof of the cycle double cover conjecture in special cases.

Circuit Double Cover of Graphs , Cun-Quan Zhang:

2-connected planar graphs

The boundary of every face of the graph is a circuit. The set of all boundaries of all faces forms a circuit double cover [Zhang, 1.1].

3-edge colorable graphs

From [Zhang, 1.3] it follows that the conjecture is true for the family of 3-edge colorable graphs since every 3-edge colorable graph is covered by three bi-colored 2-factors.

Graphs with a nowhere-zere 4-flow

Using the fact that the conjecture holds for 3-edge colorable graphs, it can be shown that it also holds for bridgeless graphs that admit a nowhere-zero 4-flow [Zhang, 7 & App. C].

The website Openproblemgarden:

Graphs with a nowhere-zere 4-flow

According to the website W.T. Tutte has also proven this, but I wasn't able to find any reference to his proof. We can however assume that it is true, because of the proof in [Zhang].

4-edge-connected graphs

F. Jaeger used the above result in combination with is 4-flow theorem to proof the conjecture for 4-edge-connected graphs.

3-edge colorable graphs

Since a cubic graph admits a nowhere-zero 4-flow if and only if it is 3-edge-colorable, the conjecture holds for 3-edge-colorable cubic graphs. By using vertex splitting arguments, it can be shown that we can reduce the problem to the set of cubic graphs that are not 3-edge colorable.

Weaker statements

Bermond, Jackson and Jaeger used Jaeger's 8-flow theorem to prove that graphs with no cut-edge have a list of circuits so that every edge is contained in exactly four.

Using Seymour's 6-flow theorem, Fan proved that graphs with no cut-edge have a list of circuits so that every edge is contained in exactly six.