A Survey & Strengthening of Barnette's Conjecture

Tait and Tutte made famous conjectures stating that all members of certain graph classes contain Hamiltonian Cycles. Although the Tait and Tutte conjectures were disproved, Barnette continued this tradition by conjecturing that all planar, cubic, 3-connected, bipartite graphs are Hamiltonian, a problem that has remained open since its formulation in the late 1960s. This paper has a twofold purpose. The rst is to provide a survey of the literature surrounding the conjecture. The second is to prove a new strengthened form of Barnette's Conjecture by showing that it holds if and only if for any arbitrary path P of length 3 that lies on a face in a planar, cubic, 3-connected, bipartite graph, there is a Hamiltonian Cycle which passes through the middle edge in P, and avoids both its leading and trailing edges. When combined with previous results, this has implications which further strengthen the conjecture. Terminology For the purpose of this paper, we assume that the reader is familiar with standard graph theoretic terminology. All graphs are undirected, with no self loops nor any multiple edges. Barnette's Conjec-ture states that all planar, cubic, 3-connected, bipartite graphs are Hamiltonian. For the sake of no