# On the hamiltonicity of the bipartite graph?

Definition A hamiltonian cycle is a cycle that visits each vertex exactly once. A graph that contains a hamiltonian cycle is called a hamiltonian graph.

Background Barnette's conjecture is a well known conjecture which deals with the hamiltonicity of 3-regular bipartite.

Question It appears that there is no conjecture that deals with the hamiltonicity of $$d$$-regular bipartite graphs when $$d\geq 4$$, my question is

Are all the connected 4-regular bipartite graphs are Hamiltonian? (or $$d$$-regular where $$d\geq 4$$)?

If not, is there any work that deals with the hamiltonicity of the connected $$d$$-regular bipartite graphs for some $$d\geq 4$$. If yes, could you please point me to some references.

Any idea (or reference) will be useful!

• @bof yes exactly, I edited the question. In fact, in order for the graph to be hamiltonian it should be connected. Commented May 3, 2017 at 14:04

The Hamiltonian cycle problem (HCP) is NP-complete in the class of $2$-connected bipartite $d$-regular graphs for each $d \ge 3$.

Proof. It is known (see Akiyama, Nishizeki, Saito, NP-Completeness of the Hamiltonian Cycle Problem for Bipartite Graphs) that HCP is NP-complete in the class of $3$-connected bipartite cubic graphs (and therefore is NP-complete in the class of $2$-connected bipartite cubic graphs). And it is clear that HCP is in NP for any graph class. Let's show a polynomial reduction of HCP in the class of $2$-connected bipartite $d$-regular graphs to HCP in the class of $2$-connected bipartite $(d+1)$-regular graphs for $d \ge 3$.

Let $G$ be a $2$-connected bipartite $d$-regular graph. Let $G_1$ and $G_2$ be two copies of $G$. Now for each vertex $v$ of $G$ we take a copy $X_v$ of complete bipartite graph $K_{d+1, d+1}$, remove an edge between vertices $u_1$ and $u_2$ and then add edges $\{\,u_1, v_1\,\}$ and $\{\,u_2, v_2\,\}$, where $v_1$ and $v_2$ are copies of $v$ in $G_1$ and $G_2$ correspondingly. It is easy to see that constructed graph $H$ is bipartite and $(d + 1)$-regular. Graph $H$ is Hamiltonian if and only if $G$ is Hamiltonian.

Let $C$ be a Hamiltonian cycle in graph $G$. Then we replace each vertex $v$ with $v_1P_vv_2$ where $P_v$ is a Hamiltonian $(u_1, u_2)$-path in $X_v$. So we get a Hamiltonian cycle in $H$.

Let $C$ be a Hamiltonian cycle in graph $H$. Then for each $v$ all vertices of $X_v$ take consequtive $2d + 2$ positions between $v_1$ and $v_2$. If we replace each such part of cycle with $v$ we get a Hamiltonian cycle in $G$. $\square$

Therefore the answer to your question is no, no and again no, for each $d \ge 3$ there are infinitely many connected bipartite $d$-regular non-Hamiltonian graphs. However almost all regular bipartite graphs are Hamiltonian. Also non-Hamiltonian such graphs are not too small. Particularly it is conjectured by Häggkvist that every $2$-connected $k$-regular bipartite graph on at most $6k$ vertices is Hamiltonian. And it is proved that every $2$-connected $k$-regular bipartite graph on at most $6k - 38$ vertices is Hamiltonian.

• Thank you for the beautiful and comprehensive answer ! Commented May 4, 2017 at 10:24