Cycle double cover
Encyclopedia
In graph-theoretic
mathematics, a cycle double cover is a collection of cycles
in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph
, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
It is an unsolved problem, posed by George Szekeres
and Paul Seymour and known as the cycle double cover conjecture, whether every bridgeless graph has a cycle double cover. The conjecture can equivalently be formulated in terms of graph embedding
s, and in that context is also known as the circular embedding conjecture.
undirected graph has a collection of cycles
such that each edge of the graph is contained in exactly two of the cycles. The requirement that the graph be bridgeless is an obvious necessary condition for such a set of cycles to exist, because a bridge cannot belong to any cycle. A collection of cycles satisfying the condition of the cycle double cover conjecture is called a cycle double cover. Some graphs such as cycle graph
s and bridgeless cactus graph
s can only be covered by using the same cycle more than once, so this sort of duplication is allowed in a cycle double cover.
is a special case of a bridgeless graph, having the additional properties that every vertex has exactly three incident edges (that is, the graph is cubic
) and that it is not possible to partition the edges of the graph into three perfect matchings (that is, the graph has no 3-edge coloring
, and by Vizing's theorem has chromatic index 4). It turns out that snarks form the only difficult case of the cycle double cover conjecture: if the conjecture is true for snarks, it is true for any graph.
observes that, in any potential minimal counterexample to the cycle double cover conjecture, all vertices must have three or more incident edges. For, a vertex with only one edge incident forms a bridge, while if two edges are incident on a vertex, one can contract them to form a smaller graph such that any double cover of the smaller graph extends to one of the original graph. On the other hand, if a vertex v has four or more incident edges, one may “split off” two of those edges by removing them from the graph and replacing them by a single edge connecting their two other endpoints, while preserving the bridgelessness of the resulting graph. Again, a double cover of the resulting graph may be extended in a straightforward way to a double cover of the original graph: every cycle of the split off graph corresponds either to a cycle of the original graph, or to a pair of cycles meeting at v. Thus, every minimal counterexample must be cubic. But if a cubic graph can have its edges 3-colored (say with the colors red, blue, and green), then the subgraph of red and blue edges, the subgraph of blue and green edges, and the subgraph of red and green edges each form a collection of disjoint cycles that together cover all edges of the graph twice. Therefore, every minimal counterexample must be a non-3-edge-colorable bridgeless cubic graph, that is, a snark.
, ruling out some snarks such as Tietze's graph
which contain triangles. Through computer searches, it is known that every cycle of length 11 or less in a cubic graph forms a reducible configuration, and therefore that any minimal counterexample to the cycle double cover conjecture must have girth at least 12.
Unfortunately, it is not possible to prove the cycle double cover conjecture using a finite set of reducible configurations. Every reducible configuration contains a cycle, so for every finite set S of reducible configurations there is a number γ such that all configurations in the set contain a cycle of length at most γ. However, there exist snarks with arbitrarily high girth, that is, with arbitrarily high bounds on the length of their shortest cycle. 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.
onto a two-dimensional cell complex. In the case of a cubic graph, this complex always forms a manifold
. The graph is said to be circularly embedded onto the manifold, in that every face of the embedding is a simple cycle in the graph. 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 circular embedding conjecture or strong embedding conjecture states that every biconnected graph
has a circular embedding onto a manifold. If so, the graph also has a cycle double cover, formed by the faces of the embedding.
For cubic graphs, biconnectivity and bridgelessness are equivalent. Therefore, the circular embedding conjecture is clearly at least as strong as the cycle double cover conjecture. However, it turns out to be no stronger. If the vertices of a graph G are expanded to form a cubic graph, which is then circularly embedded, and the expansions are undone by contracting the added edges, the result will be a circular embedding of G itself. Therefore, if the cycle double cover conjecture is true, every biconnected graph has a circular embedding. That is, the cycle double cover conjecture is equivalent to the circular embedding conjecture, even though a cycle double cover and a circular embedding are not always the same thing.
If a circular embedding exists, it might not be on a surface of minimal genus: Nguyen Huy Xuong described a biconnected toroidal graph
none of whose circular embeddings lie on a torus.
. In terms of the cycle double cover conjecture, this is equivalent to the conjecture that there exists a cycle double cover, and an orientation for each of the cycles in the cover, such that for every edge e the two cycles that cover e are oriented in opposite directions through e.
Alternatively, strengthenings of the conjecture that involve colorings
of the cycles in the cover have also been considered. 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. If true, this would imply a conjecture of W. T. Tutte
that every bridgeless graph has a nowhere-zero 5-flow.
A stronger type of embedding than a circular embedding is a polyhedral embedding, an embedding of a graph on a surface in such a way that every face is a simple cycle and every two faces that intersect do so in either a single vertex or a single edge. (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.) Thus, in view of the reduction of the cycle double cover conjecture to snarks, it is of interest to investigate polyhedral embeddings of snarks. Unable to find such embeddings, Branko Grünbaum
conjectured that they do not exist, but disproved Grünbaum's conjecture by finding a snark with a polyhedral embedding.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
mathematics, a cycle double cover is a collection of cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
in an undirected graph that together include each edge of the graph exactly twice. For instance, for any polyhedral graph
Polyhedral graph
In polyhedral combinatorics, a branch of mathematics, Steinitz's theorem is a characterization of the undirected graphs formed by the edges and vertices of three-dimensional convex polyhedra: they are exactly the 3-vertex-connected planar graphs...
, the faces of a convex polyhedron that represents the graph provide a double cover of the graph: each edge belongs to exactly two faces.
It is an unsolved problem, posed by George Szekeres
George Szekeres
George Szekeres AM was a Hungarian-Australian mathematician.-Early years:Szekeres was born in Budapest, Hungary as Szekeres György and received his degree in chemistry at the Technical University of Budapest. He worked six years in Budapest as an analytical chemist. He married Esther Klein in 1936...
and Paul Seymour and known as the cycle double cover conjecture, whether every bridgeless graph has a cycle double cover. The conjecture can equivalently be formulated in terms of graph embedding
Graph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
s, and in that context is also known as the circular embedding conjecture.
Formulation
The usual formulation of the cycle double cover conjecture asks whether every bridgelessBridge (graph theory)
In graph theory, a bridge is an edge whose deletion increases the number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle....
undirected graph has a collection of cycles
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
such that each edge of the graph is contained in exactly two of the cycles. The requirement that the graph be bridgeless is an obvious necessary condition for such a set of cycles to exist, because a bridge cannot belong to any cycle. A collection of cycles satisfying the condition of the cycle double cover conjecture is called a cycle double cover. Some graphs such as cycle graph
Cycle graph
In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
s and bridgeless cactus graph
Cactus graph
In graph theory, a cactus is a connected graph in which any two simple cycles have at most one vertex in common. Equivalently, every edge in such a graph belongs to at most one simple cycle. Equivalently, every block is an edge or a cycle.-Properties:Cacti are outerplanar graphs...
s can only be covered by using the same cycle more than once, so this sort of duplication is allowed in a cycle double cover.
Reduction to snarks
A snarkSnark (graph theory)
In the mathematical field of graph theory, a snark is a connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, and the edges cannot be colored by only three colors without two edges of the same color meeting at a...
is a special case of a bridgeless graph, having the additional properties that every vertex has exactly three incident edges (that is, the graph is cubic
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
) and that it is not possible to partition the edges of the graph into three perfect matchings (that is, the graph has no 3-edge coloring
Edge coloring
In graph theory, an edge coloring of a graph is an assignment of “colors” to the edges of the graph so that no two adjacent edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several...
, and by Vizing's theorem has chromatic index 4). It turns out that snarks form the only difficult case of the cycle double cover conjecture: if the conjecture is true for snarks, it is true for any graph.
observes that, in any potential minimal counterexample to the cycle double cover conjecture, all vertices must have three or more incident edges. For, a vertex with only one edge incident forms a bridge, while if two edges are incident on a vertex, one can contract them to form a smaller graph such that any double cover of the smaller graph extends to one of the original graph. On the other hand, if a vertex v has four or more incident edges, one may “split off” two of those edges by removing them from the graph and replacing them by a single edge connecting their two other endpoints, while preserving the bridgelessness of the resulting graph. Again, a double cover of the resulting graph may be extended in a straightforward way to a double cover of the original graph: every cycle of the split off graph corresponds either to a cycle of the original graph, or to a pair of cycles meeting at v. Thus, every minimal counterexample must be cubic. But if a cubic graph can have its edges 3-colored (say with the colors red, blue, and green), then the subgraph of red and blue edges, the subgraph of blue and green edges, and the subgraph of red and green edges each form a collection of disjoint cycles that together cover all edges of the graph twice. Therefore, every minimal counterexample must be a non-3-edge-colorable bridgeless cubic graph, that is, a snark.
Reducible configurations
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. For instance, if a cubic graph contains a triangle, a Δ-Y transform will replace the triangle by a single vertex; any cycle double cover of the smaller graph can be extended back to a cycle double cover of the original cubic graph. Therefore, a minimal counterexample to the cycle double cover conjecture must be a triangle-free graphTriangle-free graph
In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally...
, ruling out some snarks such as Tietze's graph
Tietze's graph
In the mathematical field of graph theory, the Tietze's graph is an undirected cubic graph with 12 vertices and 18 edges, formed by applying a Y-Δ transform to the Petersen graph and thereby replacing one of its vertices by a triangle....
which contain triangles. Through computer searches, it is known that every cycle of length 11 or less in a cubic graph forms a reducible configuration, and therefore that any minimal counterexample to the cycle double cover conjecture must have girth at least 12.
Unfortunately, it is not possible to prove the cycle double cover conjecture using a finite set of reducible configurations. Every reducible configuration contains a cycle, so for every finite set S of reducible configurations there is a number γ such that all configurations in the set contain a cycle of length at most γ. However, there exist snarks with arbitrarily high girth, that is, with arbitrarily high bounds on the length of their shortest cycle. 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.
Circular embedding conjecture
If a graph has a cycle double cover, the cycles of the cover can be used to form the 2-cells of a graph embeddingGraph embedding
In topological graph theory, an embedding of a graph G on a surface Σ is a representation of G on Σ in which points of Σ are associated to vertices and simple arcs are associated to edges in such a way that:...
onto a two-dimensional cell complex. In the case of a cubic graph, this complex always forms a manifold
Manifold
In mathematics , a manifold is a topological space that on a small enough scale resembles the Euclidean space of a specific dimension, called the dimension of the manifold....
. The graph is said to be circularly embedded onto the manifold, in that every face of the embedding is a simple cycle in the graph. 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 circular embedding conjecture or strong embedding conjecture states that every biconnected graph
Biconnected graph
In the mathematical discipline of graph theory, a biconnected graph is a connected graph with no articulation vertices.In other words, a biconnected graph is connected and nonseparable, meaning that if any vertex were to be removed, the graph will remain connected.The property of being 2-connected...
has a circular embedding onto a manifold. If so, the graph also has a cycle double cover, formed by the faces of the embedding.
For cubic graphs, biconnectivity and bridgelessness are equivalent. Therefore, the circular embedding conjecture is clearly at least as strong as the cycle double cover conjecture. However, it turns out to be no stronger. If the vertices of a graph G are expanded to form a cubic graph, which is then circularly embedded, and the expansions are undone by contracting the added edges, the result will be a circular embedding of G itself. Therefore, if the cycle double cover conjecture is true, every biconnected graph has a circular embedding. That is, the cycle double cover conjecture is equivalent to the circular embedding conjecture, even though a cycle double cover and a circular embedding are not always the same thing.
If a circular embedding exists, it might not be on a surface of minimal genus: Nguyen Huy Xuong described a biconnected toroidal graph
Toroidal graph
In mathematics, a graph G is toroidal if it can be embedded on the torus. In other words, the graph's vertices can be placed on a torus such that no edges cross...
none of whose circular embeddings lie on a torus.
Stronger conjectures and related problems
A stronger version of the circular embedding conjecture that has also been considered is the conjecture that every biconnected graph has a circular embedding on an orientable manifoldOrientability
In mathematics, orientability is a property of surfaces in Euclidean space measuring whether or not it is possible to make a consistent choice of surface normal vector at every point. A choice of surface normal allows one to use the right-hand rule to define a "clockwise" direction of loops in the...
. In terms of the cycle double cover conjecture, this is equivalent to the conjecture that there exists a cycle double cover, and an orientation for each of the cycles in the cover, such that for every edge e the two cycles that cover e are oriented in opposite directions through e.
Alternatively, strengthenings of the conjecture that involve colorings
Graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices share the...
of the cycles in the cover have also been considered. 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. If true, this would imply a conjecture of W. T. Tutte
W. T. Tutte
William Thomas Tutte, OC, FRS, known as Bill Tutte, was a British, later Canadian, codebreaker and mathematician. During World War II he made a brilliant and fundamental advance in Cryptanalysis of the Lorenz cipher, a major German code system, which had a significant impact on the Allied...
that every bridgeless graph has a nowhere-zero 5-flow.
A stronger type of embedding than a circular embedding is a polyhedral embedding, an embedding of a graph on a surface in such a way that every face is a simple cycle and every two faces that intersect do so in either a single vertex or a single edge. (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.) Thus, in view of the reduction of the cycle double cover conjecture to snarks, it is of interest to investigate polyhedral embeddings of snarks. Unable to find such embeddings, Branko Grünbaum
Branko Grünbaum
Branko Grünbaum is a Croatian-born mathematician and a professor emeritus at the University of Washington in Seattle. He received his Ph.D. in 1957 from Hebrew University of Jerusalem in Israel....
conjectured that they do not exist, but disproved Grünbaum's conjecture by finding a snark with a polyhedral embedding.
External links
- Cycle double cover conjecture, circular embedding conjecture, and Grünbaum's conjecture, from the Open Problem Garden.
- The Cycle Double Cover Conjecture, Dan Archdeacon.