Showing existence of hamiltonian circuit given number of vertices, edges and the minimum degree of each vertex

Question

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!

Answer 1

if $G$ has a vertex of degree two or three then by removing it you get a graph on $7$ vertices with at least 19 edges which is at most $2$ edges short from being complete. Then a hamiltonian path could be found in the new graph between two of the neighbours of the deleted vertex which with the deleted vertex will give you a hamiltonian cycle in the original graph.