# Hamiltonian Cycles and minimum vertex degrees

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.)

-

Theorem (Dirac): Let $G(V,\ E)$ be a simple graph of order $|V|\ge 3$. If each vertex $v\in V$ satisfies $\deg v \ge \frac{n}{2}$ then $G$ is Hamiltonian.
Proof Sketch: First note that the degree condition implies that $G$ is necessarily connected. Now let $$P = (v_1,\ \cdots,\ v_k)$$ denote the longest path in $G$. Necessarily, every neighbor of the end points $v_k$ and $v_1$ are contained in $P$ and that each must be connected to $\frac{n}{2}$ vertices in the path.
Since the two vertices total at least $n$ edges to the path, there must be an index $i$ such that $(v_1,\ v_{i+1})\in E$ and $(v_{i},\ v_k)\in E$. The claim is that $$C = (v_1,\ v_{i+1},\ \cdots,\ v_k,\ v_i,\ \cdots,\ v_1)$$ is a Hamiltonian cycle. If there were vertices excluded from this cycle, then pick any vertex connected to $P$ but not in $P$, say $x\notin P$ and $(x,\ v_j)\in E$. But then we can extend $P$ by starting at $x$ and cycling through $C$. This contradicts the fact that $P$ is the longest path in $G$. Therefore $G$ is Hamiltonian. $\square$