There is a connected graph with $8$ vertices and $22$ edges which has no $HC$ since $22 = \frac{(n − 1)(n − 2)}{2} + 1$ for $n = 8$.
Is there such a graph if we assume in addition that each vertex has degree at least $2$? Please provide one if it exists, or provide the argument if such graph does not exist.
Thoughts: I tried looking at the complements i.e. graphs on $8$ vertices with $6$ edges and the degree of each vertex at most $5$. But I am not 100% sure as to how I should proceed to show that a hamiltonian cycle exists!