Cycle double cover

It is an unsolved problem, posed by W. T. Tutte,[1] Itai and Rodeh,[2] George Szekeres[3] and Paul Seymour[4] and known as the cycle double cover conjecture, whether every bridgeless graph has a cycle double cover.

[5] Jaeger (1985) observes that, in any potential minimal counterexample to the cycle double cover conjecture, all vertices must have three or more incident edges.

[5] One possible attack on the cycle double cover problem would be to show that there cannot exist a minimum counterexample, by proving that any graph contains a reducible configuration, a subgraph that can be replaced by a smaller subgraph in a way that would preserve the existence or nonexistence of a cycle double cover.

[6] Unfortunately, it is not possible to prove the cycle double cover conjecture using a finite set of reducible configurations.

[7] A snark G with girth greater than γ cannot contain any of the configurations in the set S, so the reductions in S are not strong enough to rule out the possibility that G might be a minimal counterexample.

However, a cycle double cover of a graph with degree greater than three may not correspond to an embedding on a manifold: the cell complex formed by the cycles of the cover may have non-manifold topology at its vertices.

The strongest of these is a conjecture that every bridgeless graph has a circular embedding on an orientable manifold in which the faces can be 5-colored.

(In the case of a cubic graph, this can be simplified to a requirement that every two faces that intersect do so in a single edge.)