Is there a 2-connected k-regular graph without 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.


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:

enter image description here