2
$\begingroup$

Take a graph $G$ on $n\ge 4$ vertices and suppose that every vertex has degree at least $\frac12n$. Does $G$ necessarily contain a Hamiltonian cycle? (Either give a proof or provide a counter-example.)

1 Answers 1