[Math] 2-connected k-regular graph without Hamiltonian path

co.combinatoricsgraph theory

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.

Best Answer

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.

Related Question