Hamilton Cycles in 2-Connected Regular Bipartite Graphs

Häggkvist conjectured in 1976 that every 2-connected k-regular bipartite graph G on at most 6k vertices is hamiltonian. Chetwynd and Häggkvist have shown that G is hamiltonian if G has at most 4.2k vertices. The upper bound on |V(G)| was subsequently improved to 5k − 12 and then 5k − 8 by Ash and Min Aung, respectively. We shall essentially verify Häggkvist′s conjecture by showing that every 2-connected k-regular bipartite graph on at most 6k − 38 vertices is hamiltonian.