Non hamiltonian k-regular bipartite graphs

Question

For any $k \ge 3$ construct a non hamiltonian, connected k-regular bipartite graph. I have tried to find such graphs for small $k$-s but i got nothing. Can anybody help?

Answer 1

Denote by $G$ a complete bipartite graph $K_{k,k}$ without an edge. Take $k$ copies of $G$, call them $G_1,\dots,G_k$, vertices of degree $k-1$ in $G_i$ are $v_i,u_i$. Add two vertices $a,b$ and join $a$ with all $v_i$ and $b$ with all $u_i$. The new graph is connected and bipartite, but it is not Hamiltonian since after removing $a,b$ we get too many connected components.