# Does every regular, bipartite graph contain a Hamiltonian 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!

• Are you missing a necessary condition? Consider the union of two copies of $K_{2,2}$, which is not connected. Commented Jul 27, 2020 at 18:12
• yes, thank you. The graph must also have an edge connectivity $k > 1$, I added it to the question. Commented Jul 27, 2020 at 20:17

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.
• It's related to toughness for Hamiltonian cycles. I mean, the proof is just that if you delete $2r$ vertices from a path, you can get at most $2r+1$ segments, and having more edges on top of the path can only reduce the number of components. Commented Jul 29, 2020 at 6:37