Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

1 Answer

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|improve this answer
add comment

Your Answer

 
discard

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.