Cycle double cover

Last updated August 29, 2024

Unsolved problem in mathematics:

Does every bridgeless graph have a multiset of cycles covering every edge exactly twice?

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 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. The conjecture can equivalently be formulated in terms of graph embeddings, 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 bridgeless 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 graphs and bridgeless cactus graphs 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 snark 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.^[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. 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.^[5]

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 graph, 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.^[6]

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.^[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.

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 embedding 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^[5] states that every 2-vertex-connected 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, 2-vertex-connectedness and bridgelessness are equivalent. Therefore, the circular embedding conjecture is clearly at least as strong as the cycle double cover conjecture.^[5]

If a circular embedding exists, it might not be on a surface of minimal genus: Nguyen Huy Xuong described a 2-vertex-connected toroidal graph none of whose circular embeddings lie on a torus.^[5]

Stronger conjectures and related problems

A stronger version of the circular embedding conjecture that has also been considered is the conjecture that every 2-vertex-connected graph has a circular embedding on an orientable manifold. 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.^[5]

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.^[5]

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 Kochol ( 2009a , 2009b ) disproved Grünbaum's conjecture by finding a snark with a polyhedral embedding.

Notes

Related Research Articles

In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle through all its vertices". It was proposed by P. G. Tait and disproved by W. T. Tutte, who constructed a counterexample with 25 faces, 69 edges and 46 vertices. Several smaller counterexamples, with 21 faces, 57 edges and 38 vertices, were later proved minimal by Holton & McKay (1988). The condition that the graph be 3-regular is necessary due to polyhedra such as the rhombic dodecahedron, which forms a bipartite graph with six degree-four vertices on one side and eight degree-three vertices on the other side; because any Hamiltonian cycle would have to alternate between the two sides of the bipartition, but they have unequal numbers of vertices, the rhombic dodecahedron is not Hamiltonian.

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

In the mathematical field of graph theory, a snark is an undirected graph with exactly three edges per vertex whose edges cannot be colored with only three colors. In order to avoid trivial cases, snarks are often restricted to have additional requirements on their connectivity and on the length of their cycles. Infinitely many snarks exist.

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.

In graph theory, a bridge, isthmus, cut-edge, or cut arc is an edge of a graph whose deletion increases the graph's number of connected components. Equivalently, an edge is a bridge if and only if it is not contained in any cycle. For a connected graph, a bridge can uniquely determine a cut. A graph is said to be bridgeless or isthmus-free if it contains no bridges.

In the mathematical discipline of graph theory, the dual graph of a planar graph $G$ is a graph that has a vertex for each face of $G$ . The dual graph has an edge for each pair of faces in $G$ that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge $e$ of $G$ has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of $e$ . The definition of the dual depends on the choice of embedding of the graph $G$ , so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. A more general version of Vizing's theorem states that every undirected multigraph without loops can be colored with at most $Δ+µ$ colors, where $µ$ is the multiplicity of the multigraph. The theorem is named for Vadim G. Vizing who published it in 1964.

In graph theory, a nowhere-zero flow or NZ flow is a network flow that is nowhere zero. It is intimately connected to coloring planar graphs.

In the mathematical field of graph theory, a graph G is said to be hypohamiltonian if G itself does not have a Hamiltonian cycle but every graph formed by removing a single vertex from G is Hamiltonian.

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

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. That is, every convex polyhedron forms a 3-connected planar graph, and every 3-connected planar graph can be represented as the graph of a convex polyhedron. For this reason, the 3-connected planar graphs are also known as polyhedral graphs.

In graph theory, a branch of mathematics, an edge cycle cover of a graph is a family of cycles which are subgraphs of G and contain all edges of G.

In graph theory, Grinberg's theorem is a necessary condition for a planar graph to contain a Hamiltonian cycle, based on the lengths of its face cycles. If a graph does not meet this condition, it is not Hamiltonian. The result has been widely used to prove that certain planar graphs constructed to have additional properties are not Hamiltonian; for instance it can prove non-Hamiltonicity of some counterexamples to Tait's conjecture that cubic polyhedral graphs are Hamiltonian.

In the mathematical field of graph theory, the Tutte graph is a 3-regular graph with 46 vertices and 69 edges named after W. T. Tutte. It has chromatic number 3, chromatic index 3, girth 4 and diameter 8.

In geometric graph theory, a branch of mathematics, a polyhedral graph is the undirected graph formed from the vertices and edges of a convex polyhedron. Alternatively, in purely graph-theoretic terms, the polyhedral graphs are the 3-vertex-connected, planar graphs.

In graph theory, a branch of mathematics, the Herschel graph is a bipartite undirected graph with 11 vertices and 18 edges. It is a polyhedral graph, and is the smallest polyhedral graph that does not have a Hamiltonian cycle, a cycle passing through all its vertices. It is named after British astronomer Alexander Stewart Herschel, because of Herschel's studies of Hamiltonian cycles in polyhedral graphs.

Barnette's conjecture is an unsolved problem in graph theory, a branch of mathematics, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis; it states that every bipartite polyhedral graph with three edges per vertex has a Hamiltonian cycle.

The Petersen Graph is a mathematics book about the Petersen graph and its applications in graph theory. It was written by Derek Holton and John Sheehan, and published in 1993 by the Cambridge University Press as volume 7 in their Australian Mathematical Society Lecture Series.

References

Fleischner, Herbert (1976), "Eine gemeinsame Basis für die Theorie der Eulerschen Graphen und den Satz von Petersen", Monatshefte für Mathematik, 81 (4): 267–278, doi:10.1007/BF01387754, S2CID 118767538 .
Itai, A.; Rodeh, M. (1978), "Covering a graph by circuits", Automata, Languages and Programming. ICALP 1978., Lecture Notes in Computer Science (Ausiello, G., Böhm, C. (eds)), vol. 62, Springer, pp. 289–299, doi:10.1007/3-540-08860-1_21, ISBN 978-3-540-08860-8 {{citation}}: CS1 maint: date and year (link).
Huck, A. (2000), "Reducible configurations for the cycle double cover conjecture", Discrete Applied Mathematics, 99 (1–3): 71–90, doi: 10.1016/S0166-218X(99)00126-2 .
Jaeger, F. (1985), "A survey of the cycle double cover conjecture", Annals of Discrete Mathematics 27 – Cycles in Graphs, North-Holland Mathematics Studies, vol. 27, pp. 1–12, doi:10.1016/S0304-0208(08)72993-1, ISBN 978-0-444-87803-8 .
Kochol, Martin (1996), "Snarks without small cycles", Journal of Combinatorial Theory, Series B, 67 (1) (1 ed.): 34–47, doi: 10.1006/jctb.1996.0032 .
Kochol, Martin (2009a), "3-Regular non 3-edge-colorable graphs with polyhedral embeddings in orientable surfaces", Graph Drawing 2008, Editors: I.G. Tollis, M. Patrignani, Lecture Notes in Computer Science, vol. 5417, pp. 319–323.
Kochol, Martin (2009b), "Polyhedral embeddings of snarks in orientable surfaces", Proceedings of the American Mathematical Society, 137 (5) (5 ed.): 1613–1619, doi: 10.1090/S0002-9939-08-09698-6 .
Seymour, P. D. (1979), "Sums of circuits", in Bondy, J. A.; Murty, U.S.R. (eds.), Graph Theory and Related Topics, New York: Academic Press, pp. 342–355, ISBN 978-0121143503 {{citation}}: CS1 maint: date and year (link).
Szekeres, G. (1973), "Polyhedral decomposition of cubic graphs", Bulletin of the Australian Mathematical Society, 8 (3): 367–387, doi: 10.1017/S0004972700042660 .
Tutte, W. T. (1987), Personal correspondence with H. Fleischner (July 22,1987).
Zhang, Cun-Quan (1997), Integer Flows and Cycle Covers of Graphs , CRC Press, ISBN 978-0-8247-9790-4 .
Zhang, Cun-Quan (2012), Circuit Double Cover of Graphs, Cambridge University Press, ISBN 978-0-5212-8235-2 .

External links

Cycle double cover conjecture, circular embedding conjecture, and Grünbaum's conjecture, from the Open Problem Garden.
The Cycle Double Cover Conjecture Archived 2008-12-05 at the Wayback Machine , Dan Archdeacon.
Weisstein, Eric W., "Cycle Double Cover Conjecture", MathWorld

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Tutte (1987).

[2] Itai & Rodeh (1978).

[3] Szekeres (1973).

[4] Seymour (1979).

[Jaeger-5] 1 2 3 4 5 6 7 Jaeger (1985).

[6] Huck (2000).

[7] Kochol (1996).

[1]

[2]

[3]

[4]

[5]

[6]

[7]