# Is there a 2-connected k-regular graph without Hamiltonian path?

In this paper (Construction 2.6 p860) the authors have built examples of connected $k$-regular graph without Hamiltonian path, but with a cut-vertex (i.e. it is not $2$-connected).

Question: Is there a $2$-connected $k$-regular graph without Hamiltonian path?

Remark: every $2$-connected $k$-regular graph with at most $3k+3$ vertices admits a Hamiltonian cycle or is one of the two exceptions, which admit a Hamiltonian path.

Take $k>3$ long paths between two vertices $a,b$. This graph is already 2-connected. Now add some edges to make it $k$-regular so that every edge joins only interior vertices of the same path (it is not hard). Then $G\setminus\{a,b\}$ has more connected components than any graph having Hamiltonian path with two vertices removed.

• 1) The question is about paths, not cycles. 2) Start at $a$, take one of the paths to $b$, take the other path back to $a$ – isn't that a Hamiltonian cycle? – Gerry Myerson Jun 22 '16 at 22:42
• 2) I think, no, because we have $k>3$ paths between $a,b$. Well, for $k=3$ this does not work, but there exist another constructions. – Fedor Petrov Jun 22 '16 at 22:49
• OK. For $k=4$, your construction can give a graph on just 14 vertices. Very good. – Gerry Myerson Jun 22 '16 at 22:57
• I doubt, we need more vertices in paths for making graph $k$-regular. 22 vertices are enough for $k=4$. – Fedor Petrov Jun 22 '16 at 23:01
• Do you expect that $22$ is the smallest order for a $2$-connected $k$-regular non-traceable graph? – Sebastien Palcoux Jun 23 '16 at 11:08

According to this excerpt from the book Covering Walks in Graphs by Fujie & Zhang (2014), the Zamfirescu graph of order 36[1] is non-traceable (i.e.: does not contain a Hamiltonian path). Moreover, this graph is a snark and hence 3-regular and 2-connected.

The Thomassen graph of order 34[2] is also 3-regular, 2-connected, and non-traceable.

1. Zamfirescu, Tudor. "On longest paths and circuits in graphs." Mathematica Scandinavica 38.2 (1976): 211-239.

2. Thomassen, Carsten. "Hypohamiltonian and hypotraceable graphs." Discrete Mathematics 9.1 (1974): 91-96.

The smallest graph coming from the construction of Fedor Petrov's answer can be realized as follows: