Does every regular, bipartite graph contain a Hamiltonian path

bipartite-graphsgraph theoryhamiltonian-path

This may be a rather straight-forward question; however, I am unable to arrive at an answer myself.

Given a $r$-regular, $k$-edge-connected, bipartite graph, will there always be a Hamiltonian path in it (for $r \ge 2$ and $k \ge 2$)? I.e., is the graph traceable?
I am aware of Georges' Graph as already discussed in this answer, but my question would be less strict, as a Hamiltonian path does not imply a Hamiltonian cycle.

I searched in the House of Graphs with the following query

        Regular = true
AND     Bipartite = true
AND     Hamiltonian = false
AND     Edge Connectivity >= 2.0

and tried searching for Hamiltonian paths with a simple recursive search in Python. Due to the size of the graph and the NP-completeness of the problem, the search went on for hours without resulting in an answer.

I was unable to find any research papers targeted explicitly at this topic and would appreciate every advice!

Best Answer

Here's a $2$-edge-connected construction for any $r \ge 3$ that doesn't have a Hamiltonian path.

Take $r^2$ copies of $K_{r,r}$ numbered $(1,1)$ through $(r,r)$, and $2r$ more vertices $\{x_1, \dots, x_r, y_1, \dots, y_r\}$. Then, for each $1 \le i,j \le r$, delete an edge from the $(i,j)^{\text{th}}$ copy of $K_{r,r}$; connect one of its endpoints to $x_i$ and the other to $y_j$.

The resulting graph can be divided into $r^2$ components by deleting $2r$ vertices. On the other hand, a graph that contains a Hamiltonian path can only be divided into at most $2r+1$ components by deleting $2r$ vertices; contradiction.

Related Question