Barnette's conjecture
Encyclopedia
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.
is an undirected graph that can be embedded
into the Euclidean plane without any crossings
. A planar graph is called polyhedral
if and only if it is 3-vertex-connected
, that is, if there do not exist two vertices the removal of which would disconnect the rest of the graph. A graph is bipartite
if its vertices can be colored
with two different colors such that each edge has one endpoint of each color. A graph is cubic
(or 3-regular
) if each vertex is the endpoint of exactly three edges. And, a graph is Hamiltonian if there exists a cycle that passes exactly once through each of its vertices. Barnette's conjecture states that every cubic bipartite polyhedral graph is Hamiltonian.
By Steinitz's theorem
, a planar graph represents the edges and vertices of a convex polyhedron if and only if it is polyhedral.
And, a planar graph is bipartite if and only if, in a planar embedding of the graph, all face cycles have even length. Therefore, Barnette's conjecture may be stated in an equivalent form: suppose that a three-dimensional convex polyhedron has an even number of edges on each of its faces. Then, according to the conjecture, the graph of the polyhedron has a Hamiltonian cycle.
. It was disproven by , who constructed a counterexample
with 46 vertices; other researchers later found even smaller counterexamples. However, none of these known counterexamples is bipartite. Tutte himself conjectured that every cubic 3-connected bipartite graph is Hamiltonian, but this was shown to be false by the discovery of a counterexample, the Horton graph
. proposed a weakened combination of Tait's and Tutte's conjectures, stating that every bipartite cubic polyhedron is Hamiltonian, or, equivalently, that every counterexample to Tait's conjecture is non-bipartite.
Barnette's conjecture is also equivalent to the statement that the vertices of every cubic bipartite polyhedral graph can be partitioned into two subsets in such a way that every cycle of the graph passes through both subsets; that is, the graph can be covered by two induced forests
.
If Barnette's conjecture turns out to be false, then it can be shown to be NP-complete
to test whether a bipartite cubic polyhedron is Hamiltonian. If a planar graph is bipartite and cubic but only 2-connected, then it may be non-Hamiltonian, and it is NP-complete to test Hamiltonicity for these graphs.
Conjecture
A conjecture is a proposition that is unproven but is thought to be true and has not been disproven. Karl Popper pioneered the use of the term "conjecture" in scientific philosophy. Conjecture is contrasted by hypothesis , which is a testable statement based on accepted grounds...
in graph theory
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...
, a branch of mathematics
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, concerning Hamiltonian cycles in graphs. It is named after David W. Barnette, a professor emeritus at the University of California, Davis
University of California, Davis
The University of California, Davis is a public teaching and research university established in 1905 and located in Davis, California, USA. Spanning over , the campus is the largest within the University of California system and third largest by enrollment...
; it states that every bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
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...
with three edges per vertex
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....
has a Hamiltonian cycle.
Definitions
A planar graphPlanar graph
In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...
is an undirected graph that can be embedded
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:...
into the Euclidean plane without any crossings
Crossing number (graph theory)
In graph theory, the crossing number cr of a graph G is the lowest number of edge crossings of a planar drawing of the graph G. For instance, a graph is planar if and only if its crossing number is zero.The concept originated in...
. A planar graph is called polyhedral
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...
if and only if it is 3-vertex-connected
K-vertex-connected graph
In graph theory, a graph G with vertex set V is said to be k-vertex-connected if the graph remains connected when you delete fewer than k vertices from the graph...
, that is, if there do not exist two vertices the removal of which would disconnect the rest of the graph. A graph is bipartite
Bipartite graph
In the mathematical field of graph theory, a bipartite graph is a graph whose vertices can be divided into two disjoint sets U and V such that every edge connects a vertex in U to one in V; that is, U and V are independent sets...
if its vertices can be colored
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...
with two different colors such that each edge has one endpoint of each color. A 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....
(or 3-regular
Regular graph
In graph theory, a regular graph is a graph where each vertex has the same number of neighbors; i.e. every vertex has the same degree or valency. A regular directed graph must also satisfy the stronger condition that the indegree and outdegree of each vertex are equal to each other...
) if each vertex is the endpoint of exactly three edges. And, a graph is Hamiltonian if there exists a cycle that passes exactly once through each of its vertices. Barnette's conjecture states that every cubic bipartite polyhedral graph is Hamiltonian.
By Steinitz's theorem
Steinitz's theorem
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...
, a planar graph represents the edges and vertices of a convex polyhedron if and only if it is polyhedral.
And, a planar graph is bipartite if and only if, in a planar embedding of the graph, all face cycles have even length. Therefore, Barnette's conjecture may be stated in an equivalent form: suppose that a three-dimensional convex polyhedron has an even number of edges on each of its faces. Then, according to the conjecture, the graph of the polyhedron has a Hamiltonian cycle.
History
In conjectured that every cubic polyhedral graph is Hamiltonian; this came to be known as Tait's conjectureTait's conjecture
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 and disproved by , who constructed a counterexample with 25 faces, 69 edges and 46 vertices...
. It was disproven by , who constructed a counterexample
Counterexample
In logic, and especially in its applications to mathematics and philosophy, a counterexample is an exception to a proposed general rule. For example, consider the proposition "all students are lazy"....
with 46 vertices; other researchers later found even smaller counterexamples. However, none of these known counterexamples is bipartite. Tutte himself conjectured that every cubic 3-connected bipartite graph is Hamiltonian, but this was shown to be false by the discovery of a counterexample, the Horton graph
Horton graph
In the mathematical field of graph theory, the Horton graph or Horton 96-graph is a 3-regular graph with 96 vertices and 144 edges discovered by Joseph Horton...
. proposed a weakened combination of Tait's and Tutte's conjectures, stating that every bipartite cubic polyhedron is Hamiltonian, or, equivalently, that every counterexample to Tait's conjecture is non-bipartite.
Equivalent forms
showed that Barnette's conjecture is equivalent to a stronger statement, that for every two edges e and f on the same face of a bipartite cubic polyhedron, there exists a Hamiltonian cycle that contains e but does not contain f. Clearly, if this stronger statement is true, then every bipartite cubic polyhedron contains a Hamiltonian cycle: just choose e and f arbitrarily. In the other directions, Kelman showed that a counterexample to this stronger conjecture could be transformed into a counterexample to the original Barnette conjecture.Barnette's conjecture is also equivalent to the statement that the vertices of every cubic bipartite polyhedral graph can be partitioned into two subsets in such a way that every cycle of the graph passes through both subsets; that is, the graph can be covered by two induced forests
Tree (graph theory)
In mathematics, more specifically graph theory, a tree is an undirected graph in which any two vertices are connected by exactly one simple path. In other words, any connected graph without cycles is a tree...
.
Partial results
Although the truth of Barnette's conjecture remains unknown, computational experiments have shown that there is no counterexample with fewer than 86 vertices.If Barnette's conjecture turns out to be false, then it can be shown to be NP-complete
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
to test whether a bipartite cubic polyhedron is Hamiltonian. If a planar graph is bipartite and cubic but only 2-connected, then it may be non-Hamiltonian, and it is NP-complete to test Hamiltonicity for these graphs.
Related problems
A related conjecture of Barnette states that every cubic polyhedral graph in which all faces have six or fewer edges is Hamiltonian. Computational experiments have shown that, if a counterexample exists, it would have to have more than 177 vertices.External links
- Barnette's Conjecture in the Open Problem Garden, Robert Samal, 2007.