Hamiltonicity and minimal degree in bipartite graphs

Question

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

1. $|A| = |B|$,
2. $\text{deg}(v) \geq k$ for all $v\in A\cup B$, and
3. there is no Hamiltonian path in $\Gamma$

?

Answer 1

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?)

Answer 2

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$.)