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!
Best Answer
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.