Barnette's conjecture is an unsolved problem in

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conn ...

, a branch of mathematics, concerning

Hamiltonian cycle In the mathematical field of graph theory, a Hamiltonian path (or traceable path) is a path in an undirected or directed graph that visits each vertex exactly once. A Hamiltonian cycle (or Hamiltonian circuit) is a cycle that visits each vertex ...

s in graphs. It is named after David W. Barnette, a

professor emeritus ''Emeritus'' (; female: ''emerita'') is an adjective used to designate a retired chair, professor, pastor, bishop, pope, director, president, prime minister, rabbi, emperor, or other person who has been "permitted to retain as an honorary title ...

at the

University of California, Davis The University of California, Davis (UC Davis, UCD, or Davis) is a public land-grant research university near Davis, California. Named a Public Ivy, it is the northernmost of the ten campuses of the University of California system. The inst ...

; it states that every bipartite

polyhedral graph 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-con ...

with three edges per vertex has a Hamiltonian cycle.

Definitions

A planar graph is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' ve ...

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 ''Colored'' (or ''coloured'') is a racial descriptor historically used in the United States during the Jim Crow Era to refer to an African American. In many places, it may be considered a slur, though it has taken on a special meaning in Sout ...

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. Finally, a graph is

Hamiltonian Hamiltonian may refer to: * Hamiltonian mechanics, a function that represents the total energy of a system * Hamiltonian (quantum mechanics), an operator corresponding to the total energy of that system ** Dyall Hamiltonian, a modified Hamiltonian ...

if there exists a cycle that passes through each of its vertices exactly once. 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 A convex polytope is a special case of a polytope, having the additional property that it is also a convex set contained in the n-dimensional Euclidean space \mathbb^n. Most texts. use the term "polytope" for a bounded convex polytope, and the wo ...

if and only if it is polyhedral. A three-dimensional polyhedron has a cubic graph if and only if it is a

simple polyhedron In geometry, a -dimensional simple polytope is a -dimensional polytope each of whose vertices are adjacent to exactly edges (also facets). The vertex figure of a simple -polytope is a -simplex. Simple polytopes are topologically dual to si ...

. 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 simple

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

conjectured that every cubic polyhedral graph is Hamiltonian; this came to be known as

Tait's conjecture In mathematics, Tait's conjecture states that "Every 3-connected planar cubic graph has a Hamiltonian cycle (along the edges) through all its vertices". It was proposed by and disproved by , who constructed a counterexample with 25 faces, 69 e ...

. It was disproven by , who constructed a

counterexample A counterexample is any exception to a generalization. In logic a counterexample disproves the generalization, and does so rigorously in the fields of mathematics and philosophy. For example, the fact that "John Smith is not a lazy student" is a ...

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.

Equivalent forms

showed that Barnette's conjecture is equivalent to a superficially 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 statement is true, then every bipartite cubic polyhedron contains a Hamiltonian cycle: just choose ''e'' and ''f'' arbitrarily. In the other directions, Kelmans showed that a counterexample could be transformed into a counterexample to the original Barnette conjecture. Barnette's conjecture is also equivalent to the statement that the vertices of the dual of every cubic bipartite polyhedral graph can be partitioned into two subsets whose

induced subgraph In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

s are trees. The cut induced by such a partition in the dual graph corresponds to a Hamiltonian cycle in the primal graph.

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 In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by trying ...

to test whether a bipartite cubic polyhedron is Hamiltonian. If a planar graph is bipartite and cubic but only of connectivity 2, then it may be non-Hamiltonian, and it is NP-complete to test Hamiltonicity for these graphs. Another result was obtained by : if the dual graph can be vertex-colored with colors blue, red and green such that every red-green cycle contains a vertex of degree 4, then the primal graph is Hamiltonian.

Notes

References

* * * * * * * * * * * * *; Reprinted in ''Scientific Papers'', Vol. II, pp. 85–98 * *

External links

*{{mathworld, title=Barnette's Conjecture, urlname=BarnettesConjecture, mode=cs2
Barnette's Conjecture
in the Open Problem Garden, Robert Samal, 2007. Conjectures Unsolved problems in graph theory Planar graphs Hamiltonian paths and cycles