# Smallest non-hamiltonian k-connected graph

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 ?

• Notice that every Hamiltonian graph is $2$-connected so this question only makes sense for $k \ge 3$ – Jernej Sep 8 '14 at 11:25
• The smallest example for $k=3$ has 7 vertices. – Jernej Sep 8 '14 at 11:33
• Nevermind - I misunderstood the question. The comment about $k=3$ is still valid though. – Jernej Sep 8 '14 at 11:34
• – Jernej Sep 8 '14 at 11:41

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.