0
$\begingroup$

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!

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.