Let $G$ be a simple undirected $k$-connected graph with at least $k+1$ vertices.
What ist the least number of vertices, $G$ can have, if it is not hamiltonian ?
I know Tutte's theorem that every $4$-connected planar graph is hamiltonian, so for $k\ge 4$ only non-planar graphs are possible.
A lower bound for the number of vertices is $2k+1$ because in a k-connected graph, every vertex has degree at least k, so if the number of vertices is not exceeding $2k$, it must be hamiltonian.
I am not quite sure, if a graph with the desired property exists for all $k$. If not, what is the least $k$, such that no graph with the desired property exists ?
The complete bipartite graph $K_{k,k+1}$ has $2k+1$ vertices and is $k$ connected, but is not Hamiltonian since any path must travel alternately between the two sets of the bipartition and there are not the same number of vertices in each side.