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
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 email@example.com)
Send comments to firstname.lastname@example.org