Barnette's Conjecture: Hamiltonian Cycles in Planar Bipartite Graphs

---

---

It is not too hard to show that if every 3-connected cubic planar graph is Hamiltonian, then the Four-Color-Theorem is true. However, Tutte found a 3-connected cubic planar graph that was not Hamiltonian. Barnette asked if there was such an example that was bipartite.

Problem:  Is every 3-connected 3-regular planar bipartite graph Hamiltonian?

The Hershal graph is bipartite with a different number of vertices in each partite set, so it shows that the hypothesis “cubic” is necessary. If the graph is 4-connected, then it has a Hamiltonian cycle by the theorem of Tutte.

---

Submitted by: Dan Archdeacon (with thanks to hochberg@dimacs.rutgers.edu)

Send comments to dan.archdeacon@uvm.edu

November, 2003

---

---