Hamiltonian cycles in bipartite toroidal graphs with a partite set of degree four vertices

AbstractLet G be a 3-connected bipartite graph with partite sets X∪Y which is embeddable in the torus. We shall prove that G has a Hamiltonian cycle if (i) G is balanced, i.e., |X|=|Y|, and (ii) each vertex x∈X has degree four. In order to prove the result, we establish a result on orientations of quadrangular torus maps possibly with multiple edges. This result implies that every 4-connected toroidal graph with toughness exactly one is Hamiltonian, and partially solves a well-known Nash-Williamsʼ conjecture