**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