# Maximum minimal degree $\delta(G)$ for connected, non-Hamiltonian $G$

For a finite, simple undirected graph $G=(V,E)$ let $\delta(G)$ denote the minimum degree of all vertices. For any integer $k\geq 4$ let $N(k)$ denote the maximum $\delta(G)$ that a connected graph $G$ on $k$ vertices can have such that $G$ does not have a Hamiltonian path.

Do we have $\lim \sup_{k\to \infty} \frac{N(k)}{k} = 1$?

No, a graph with $\delta(G)\geqslant (k-1)/2$ has Hamiltonian path by Dirac's theorem. But for $\delta(G)=(k-2)/2$ this is already not always so, see $K_{m,m+2}$.
• A minor nitpick, but $K_{m,m+1}$ does have a Hamiltonian path. – Gordon Royle Apr 5 '17 at 12:27