Like many great questions in math, the Cycle Double Cover Conjecture (C.D.C.C.) has the distinction of being relatively easy to state, but quite difficult to prove. It was proposed independently by two mathematicians, George Szekeres [7] and Paul Seymour [6], in the 1970s. As of this writing, it has withstood all attempts at a solution.

A problem in graph theory, C.D.C.C. can be stated as follows:

Conjecture 1: Every bridgeless graph has a collection of cycles such that each edge of the graph is contained in exactly two of those cycles.

We only need a few definitions to understand this statement.

A cycle is 2-regular connected graph. We call a graph k-regular if every one of its vertices has k incident edges. In a connected graph, there exists a continuous path along its edges between any two of its vertices.

A bridge is an edge of a graph whose deletion increases the graph’s number of connected components. We can equivalently define an edge as a bridge if and only if it is not contained in any cycle. An edge-cut is a set of edges that, if removed, disconnects the graph. A bridge is thus an edge cut of size one.

And that’s it. So why has this straightforward-sounding problem resisted solution for so long? Let’s explore possible attacks on the C.D.C.C. and see where they fall short.

The Curious Case of Snarks

One way to prove that a conjecture is true, is to show that a counterexample to that conjecture cannot exist. This approach has been studied in the context of the C.D.C.C. In fact, we know that if a counterexample to the C.D.C.C. does exist, the minimal such graph must be something called a snark.

The first snark was uncovered in 1886 by the English mathematician A.B. Kempe, but is known as the Petersen graph, after it was rediscovered by the Danish mathematician Julius Petersen in 1898. The second and third snarks weren’t discovered until 1948 by the Croatian Danilo Blanuša. Since then, infinite classes of snarks, such as the flower snarks, have been confirmed to exist.

Snarks have a habit of surfacing in connection with important problems in graph theory besides the C.D.C.C. For example, no snark can be embedded in a plane without its edges crossing over each other if and only if the four color theorem is true (which it is).

Given their cryptic importance, Martin Gardner, the author of the “Mathematical Games” column in Scientific American, dubbed these graphs snarks, in reference to the enigmatic creature pursued by the characters in Lewis Carroll’s The Hunting of the Snark.

Snarks are defined as follows:

A snark is a simple, cubic, cyclically-4-edge-connected graph with chromatic index 4. Although not always given as part of the definition, snarks are also usually required to have a girth greater than or equal to 5.

Let’s unpack this definition. A simple graph has no more than a single edge connecting any two vertices and does not have loops, or edges starting and ending at the same vertex.

A cubic graph is one whose vertices all have degree three (every vertex has three incident edges).

A graph is cyclically-k-edge-connected if it is connected, and the removal of at least kedges of the graph is necessary to create two disconnected components, each containing a cycle.

The chromatic index of a graph is the minimum number of colors with which we can color the edges of the graph, such that no two edges with the same color meet at a vertex.

Lastly, the girth of a graph is the size of the smallest cycle in the graph.

So why must the minimal counterexample to the C.D.C.C., if it exists, be a snark? We provide a proof below.

Theorem 1: If a counterexample to the C.D.C.C. exists, the minimal such graph must be a snark.

Proof: Let G be a minimal counterexample to the C.D.C.C. Thus, G is bridgeless, has no cycle double cover (C.D.C.), and has fewer edges than any other graph with the previous two properties.

G must also be connected, since otherwise we could delete all components except the smallest one, and be left with a smaller counterexample to C.D.C.C. than G. The fact that G is connected implies that it is 2-connected (a graph is k-connectedif it has more than k vertices and removing fewer than k vertices does not separate it into multiple components). This is because a graph which is bridgeless but not 2-connected can be separated into two smaller graphs by removing one vertex, where each of the smaller graphs must have a C.D.C. which could easily be extended to a C.D.C. of G, which would mean G is not a minimal counterexample. This is illustrated in the image below.

We also observe that G must not have any loops, since we could remove them to get a smaller counterexample to C.D.C.C.

Assume G has an edge-cut of size two. If we contract one edge of this cut, we obtain a bridgeless graph G`with fewer edges than G. But then G` will have a C.D.C. which we can extend to get a C.D.C. of G — a contradiction. Thus G must be 3-edge-connected (a graph is k-edge-connected if removing fewer than k edges does not disconnect it). This means that G must also not have any vertices of degree less than three, since otherwise an edge cut of size two would exist.

Now assume that G has a vertex v of degree greater than three. We can delete two edges e1 and e2 which are incident to v, and then draw a new edge between the two vertices (not including v) to which e1 and e2 had previously been connected. The resulting graph G` is bridgeless and, because it has fewer edges than G, has a C.D.C. We can then obtain a C.D.C. of G from the C.D.C. of G` — a contradiction. G must therefore be cubic.

Next, we assume that G has a nontrivial edge-cut of size three, such that it gives a bipartition of the vertices of G into two sets, each containing more than one vertex. We then connect each of these sets to one vertex each rather than to each other, and thus get two graphs, G` and G`` as depicted below. Each of these graphs has fewer edges than G, and so both have a C.D.C. We can then stitch the C.D.C.s from G` and G`` together to get a C.D.C. for G — yet another contradiction. G is therefore cyclically-4-edge-connected.

G cannot have chromatic index equal to 3, since if it did, we could construct a C.D.C. of G where the cycles would all consist of paths made up of two alternating colors. This means that if we have red, green, and blue edges, and we start traveling along a green edge, we then choose the blue edge at the first vertex, the green edge at the second vertex, etc. until we are forced to return to the original edge. We can thus cover all edges twice with the three types of cycles made up of the three possible pairs of colors. This is a contradiction, and so G must have a chromatic index equal to four.

So the minimal counterexample to C.D.C.C. is a simple graph which must be cubic, cyclically-4-edge-connected and have a chromatic index of 4, i.e. a snark. □

One way to prove the C.D.C.C., if it is true, would be to extend this proof. We could continue to find more properties of a minimal counterexample until we discover two that contradict each other, thus proving such a counterexample does not exist.

We can also ask what girth a minimal counterexample must have. For instance, we know from work by mathematician Andreas Huck in [3] that a minimal counterexample to the C.D.C.C. must have a girth of at least 12. This is because we have found reducible configurations in all graphs with smaller girths than this.

Reducible configurations in a graph G are subgraphs that can be replaced by smaller subgraphs to create a graph G`, such that if G has a C.D.C. then G` has a C.D.C., and if G does not have a C.D.C., then G` does not have a C.D.C.

One well known example of a reducible configuration is the Δ-Y transform, which is also used in the study of electrical circuits. It’s name illustrates the transform, since we are replacing a triangle subgraph with a Y-shaped subgraph (or vice versa).

A computer-search was used in [3] to determine that there exist reducible configurations in graphs of girth no greater than 11. So if a counterexample to C.D.C.C. with girth no greater than 11 existed, we could use a reducible configuration to get a smaller graph with a C.D.C., and then extend that C.D.C. back to the original graph — a contradiction.

This approach will not be enough to let us determine the validity of the C.D.C.C. though. Although it can help us eliminate some types of graphs as potential counterexamples, mathematician Martin Kochol showed in [5] that there are snarks with arbitrarily large girth. So given a finite set of reducible configurations, we can always find a snark with a large-enough girth such that it does not contain any of the reducible configurations in our set. We thus cannot use any finite set of reducible configurations to check if the C.D.C.C. holds for all snarks.

Another way to attack the C.D.C.C. involves looking at it in a different setting.

Strongly-Embedded Graphs

Sometimes a problem becomes less difficult when we transfer it into another environment. This relocation can give us access to a new toolkit with which we can work on possible solutions.

We can pursue this strategy with the C.D.C.C., since we can show that it is equivalent to the Strong Embedding or Circular Embedding Conjecture. The Strong Embedding Conjecture (S.E.C.) is as follows:

Conjecture 2: Every biconnected graph has a strong embedding in some surface.

Let’s first give the definitions necessary to understand this statement.

A graph is biconnected if it is both connected and remains connected when one vertex is removed (all graphs which are 2-connected are biconnected; the only biconnected graph which is not 2-connected is the graph with two vertices connected by a single edge, since it does not have more than two vertices).

A surface is a closed, connected, Hausdorff topological space where every point has an open neighborhood that is homeomorphic to an open subset of the Euclidean plane; equivalently, a surface is a compact, connected 2-manifold. In the interest of staying on topic, I won’t delve into these and some other topological terms in this article (although maybe I will in a future article), but you can find their definitions in any introductory textbook on topology or on wikipedia. A sphere, a torus, and the Euclidean plane are all examples of surfaces.

An embedding of a graph G = (V, E) in a surface is a representation of G which associates distinct points on the surface with each vertex in V and associates simple arcs on the surface with each edge in E (simple arcs are homeomorphic to [0,1]). The endpoints of each simple arc correspond to the vertices at the ends of that arc’s corresponding edge in the graph. Simple arcs only intersect each other at their endpoints, and each simple arc only intersects two of the points on the surface associated with vertices (its own endpoints).

A face is a connected component which is a subset of the embedding surface that is disjoint from the graph embedding.

A 2-cell embedding is a graph embedding where every face is homeomorphic to an open disk. A strong embedding is a 2-cell embedding where the boundary of every face is a cycle of the embedded graph; equivalently, the closure of every face in a strong embedding is homeomorphic to a closed disk.

Now that we have the required definitions, let’s determine why the S.E.C. is equivalent to the C.D.C.C.

Theorem 2: The S.E.C. is equivalent to the C.D.C.C.

Proof: If the S.E.C. is true, then the C.D.C.C. must be true since we can take the boundaries of each face in the strong embedding of a graph as the cycles in a C.D.C. of that graph.

The second direction of the equivalence is slightly less trivial to prove. First we restrict ourselves to strong embeddings of cubic graphs.

If the C.D.C.C. is true, then the S.E.C. for cubic graphs must be true since we can make each cycle of a graph the boundary of a 2-cell (face). This is only possible if every point of our space has a neighborhood homeomorphic to the Euclidean plane. The three types of points possible in our space exist either in the interior of a face, the interior of an edge or at a vertex. The first two types of points clearly have neighborhoods that are homeomorphic to the Euclidean plane. The points that exist at a vertex could be problematic if we could cover them with cycles in multiple ways. But because we have restricted ourselves to cubic graphs, there is only one way to cover the three edges incident to a vertex with three cycles.

In order to extend beyond just strongly embedding cubic graphs, we use the fact that we can expand the vertices of any graph to get a cubic graph. Once we have converted a graph into a cubic graph in this way, we can then strongly embed it. Finally, we contract the edges that we added, and we are left with a strong embedding of our original graph. □

Now we have transferred the problem to the realm of topological graph theory, and we have the tools of topology at our disposal. When studying graph embeddings, an important property is the genus of a graph. Informally, the genus of a surface is the number of holes it has. The genus of a graph is the minimum integer k such that the graph can be embedded in a surface of genus k.

Interestingly, the genus of a graph is not necessarily the same as the genus required for a strong embedding of a graph. The first example discovered of this phenomenon was provided by the mathematician Nguyen Huy Xuong, and is depicted below.

One tool that has been developed to work with graph embeddings is something called a rotation system. A rotation system is a pair of permutations (σ,ρ) which act on a ground set of darts D. Each edge has two darts, one associated to each endpoint of the edge. The permutation σ(d) gives the other dart of the same edge, where d∈D. The permutation ρ(d) gives the next dart sitting clockwise relative to d around a particular vertex (the edges are cyclically-ordered about each vertex to which they are incident). The surface is thus oriented, in order to determine the clockwise direction.

If you are familiar with abstract algebra, you might have noticed that the pair of permutations (σ,ρ) generates a group <σ,ρ> on D. When reconstructing an embedding from a rotation system, you draw one edge for each orbit of σ, and one vertex for each orbit of ρ. You connect an edge to a vertex if the orbit of σ for the edge intersects the orbit of ρ for the vertex.

Rotation systems thus let us describe embeddings, and therefore C.D.C.s, in a structured way. We can use this structure to explore the properties of embeddings, and investigate transformations of embeddings that might lead us to strong embeddings. This approach has been studied since at least the late 1970s. Although it has not resolved the C.D.C.C., it has become an important framework for studying other questions in topological graph theory.

Strengthening the Problem

Another strategy we can pursue when attacking the C.D.C.C. is to strengthen the problem, a tactic that may appear counter-intuitive at first. After all, wouldn’t strengthening a problem make it more difficult to solve? In many cases the answer is yes. But it is also possible that this approach could help us realize that our problem is a special case of a more far-reaching question. This might make tools available to us that we wouldn’t otherwise know we could use.

One step in this path to strengthening the C.D.C.C. and S.E.C. is to require that they follow a particular orientation. The Orientable C.D.C.C. is as follows:

Conjecture 3: Every bridgeless graph has a C.D.C. such that the cycles are oriented so that each edge is traversed exactly once in each direction.

Similarly, the Orientable S.E.C. is:

Conjecture 4: Every biconnected graph has an orientable strong embedding into some orientable manifold.

Just like the C.D.C.C. and S.E.C., these two conjectures are also equivalent.

Theorem 3: The Orientable C.D.C.C. is equivalent to the Orientable S.E.C.

Proof: If the Orientable S.E.C. is true, then the Orientable C.D.C.C. must be true. This is because we can just traverse all face boundaries, which we use as cycles, in the direction given by the oriented manifold.

If the Orientable C.D.C.C. is true, then the Orientable S.E.C. must be true, since we can use the same argument as in the proof that the C.D.C.C. implies the S.E.C., except now we add the orientations to the embedding at the end, making sure they align with the orientation of the manifold. □

We can strengthen the C.D.C.C. again. First we need to define some new terms though.

An embedding of a graph is face-k-colorable if no two faces that share the same edge also share the same color. An n-cycle-m-cover is a collection of n cycles covering each edge exactly m times.

We now state Kirchhoff’s Law in the context of graphs. Let G=(V,E) be a directed graph and T an abelian group. A map ψ: E→T is a T-circulation if for every vertex v∈V we have:

where

and e∈E for all e.

If ψ(e)≠0 for every e∈E, we call ψ a nowhere-zero flow. If k is a positive integer and 0<|ψ(e)|<k, then ψ is a k-flow or a nowhere-zero k-flow.

Now we can state a theorem which leads us to strengthenings of the C.D.C.C.:

Theorem 4: The following statements are equivalent for a graph G:

1. G has a 3-cycle double cover
2. G has a 4-cycle double cover
3. G has a nowhere zero 4-flow

We do not provide a proof of this theorem here but one can be found in a paper by mathematician Francois Jaeger ([4]). This theorem leads us to the following conjectures:

Conjecture 5: Every biconnected graph has a face-5-colorable embedding in
an orientable surface.

This conjecture obviously implies the following conjecture:

Conjecture 6: Every bridgeless graph has a 5-cycle double cover.

We are thus left with this strengthening of the C.D.C.C.:

Conjecture 7: Every biconnected graph has a strong, face-5-colorable
embedding into an orientable surface.

This strengthening is important because if it is true, it implies that another important open problem in graph theory, Tutte’s 5-Flow Conjecture, is also true. Tutte’s 5-Flow Conjecture is as follows:

Conjecture 8: Every bridgeless graph has a nowhere-zero 5-flow.

We now prove the following theorem:

Theorem 5: If a biconnected graph has a strong, face-5-colorable embedding into an orientable surface, then it has a nowhere-zero 5-flow.

Proof: If a graph G has a face-5-coloring, we label the five colors with the numbers {0,1,2,3,4}. Given G’s orientable embedding, we construct a flow around the boundary of each face respecting the embedding surface’s orientation. We set the magnitude of the flow around a particular face equal to the number assigned to that face’s color. This is clearly a flow modulo 5. Also since no two adjacent faces have the same color, we cannot get pairs of numbers at any edge that sum to zero. Thus we have a nowhere-zero 5-flow. □

So after strengthening the C.D.C.C. we have discovered a connection to another important question in graph theory. Finding links between open problems can help us understand the landscape in which these problems live. This exploration of the problem space will hopefully help us uncover techniques whose application to one conjecture can be useful in attacking the other.

The approaches described in this article — looking for the (non)existence of a counterexample, transporting the problem into another environment, and strengthening the problem to look for connections to other topics — have so far not yielded a solution to the C.D.C.C. Whether they alone will lead us to a solution, or whether a new technique is required, they have already expanded our understanding of graph theory in fundamental ways. Hopefully at least some of them are critical steps on the road to resolving this long-standing question.

References

[1] Melody Chan. A survey of the cycle double cover conjecture. July 2009.

[2] Rani Hod, An Huang, Mark Kempton, and Shing-Tung Yau. Two conjectures on strong embeddings and 2-isomorphism for graphs.

[3] Andreas Huck. Reducible configurations for the cycle double cover conjecture. Discrete Applied Mathematics, 99:71–90, February 2000.

[4] Francois Jaeger. A survey of the cycle double cover conjecture. Annals of Discrete Mathematics, 27:1–12, January 1985.

[5] Martin Kochol. Snarks without small cycles. Journal of Combinatorial Theory, 67:34–47, May 1996.

[6] Paul D. Seymour. Disjoint paths in graphs. Discrete Mathematics, 29(3):293–309, 1980.

[7] George Szekeres. Polyhedral decomposition of cubic graphs. Bulletin of the Australian Mathematical Society, 8(3):367–387, June 1973.

[8] Wikipedia contributors. Cycle double cover — Wikipedia, the free encyclopedia, 2020. [Online; accessed 2-October-2020].