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

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!

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.