Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question

This is a very famous theorem due to Dirac. I will sketch the proof here. You can easily find more detailed proofs online.

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$

share|cite|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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