Hamiltonicity and minimal degree in bipartite graphs Given an integer $k>1$, is there a connected bipartite graph $\Gamma = (A, B, E)$ where $A\cap B = \emptyset$ and $E \subseteq \big\{\{a, b\}:a\in A, b\in B\big\}$ such that 


*

*$|A| = |B|$, 

*$\text{deg}(v) \geq k$ for all $v\in A\cup B$, and

*there is no Hamiltonian path in $\Gamma$


?
 A: Take any $k\ge 1$ and four disjoint sets of vertices $A,B,C,D$ with $|A|=|D|=k+2$, $|B|=|C|=k$. Completely join $A$ to $B$, $B$ to $C$ and $C$ to $D$.  This gives a bipartite graph of minimum degree $k$ with no hamiltonian path. (Proof: Consider how a hamiltonian path can choose edges between $A$ and $B$.)
A: The answer is yes. 
One may construct a family of examples of $\Gamma$ with the minimal 
degree equal to $2$, as follows. 


*

*For even integers $a$ and $b$, start with two even cycles $C_a$ and $C_b$. 

*On cycles $C_a$ and $C_b$, select pairs of non-adjacent vertices $u,v$ and $u′,v′$, respectively, such that both distances are of the same-parity. 

*Connect both cycles by two edges $uu′$ and $vv′$.

*Subdivide both mentioned edges $uu′$ and $vv′$ by vertices $u^*$ and $v^*$, respectively. 


First notice that if there exists a Hamiltonian path in $\Gamma$, call it $P=p_1,\dots,p_{a+b+2}$, it may not start/end with $u^*$ or $v^*$. Indeed, wlog. suppose $p_1=v^*$ and $p_2=v$, and notice that if our path $P$ covers both (non-trivial) paths from $v$ to $u$ in $C_a$, then $C_b \cup P=\emptyset$, a contradiction.
We may hence, wlog., assume that $p_1$ and $p_{a+b+2}$ both lie in $C_a$. So take now a sub-sequence $P'=P\cap C_b$ and notice that $P'$ corresponds to a Hamiltonian path in $C_b$, with endpoints in $u'$ and $v'$. Since $d_{C_b}(u',v')>1$, this is a contradiction.
A small example with $a=b=4$ is drawn below. (can someone tell me how to make it look smaller?)

