Tutte conjectured that every cubic, bipartite, 3-connected graph is Hamiltonian. It is also natural to consider Tutte's conjecture for cubic, bipartite, cyclically 4-connected graphs.

We describe constructions of cubic, bipartite, 3-connected graphs having no Hamiltonian cycle. Some of these constructions provide (infinitely many) graphs that are not both 3-connected and cyclically 4-connected. The minimal such graph has 50 vertices, and this is the smallest known counterexample to Tutte's conjecture.

Moreover, using these constructions we prove that if Barnette's conjecture (every cubic, bipartite, 3-connected planar graph is Hamiltonian) is true,
then a much stronger result is also true. We also proved with M. Lomonosov that all cubic, bipartite, 3-connected graphs with at most 30 vertices are Hamiltonian.