A note on Barnette's Conjecture
A note on Barnette's Conjecture
Barnette conjectured that each planar, bipartite, cubic, and 3-connected graph is hamiltonian.We prove that this conjecture is equivalent to the statement that there is a constant c > 0 such that each graph G of this class contains a path on at least c|V (G)| vertices.