Dirac's Theorem

From ProofWiki
Jump to navigation Jump to search

Theorem

If a connected graph $G$ has $n \ge 3$ vertices and the degree of each vertex is at least $\dfrac n 2$, then $G$ is Hamiltonian.


Proof 1

Let $P = p_1 p_2 \ldots p_k$ be the longest path in $G$.

If $p_1$ is adjacent to some vertex $v$ not in $P$, then the path $v p_1 p_2 \ldots p_k$ would be longer than $P$, contradicting the choice of $P$.

The same argument can be made for $p_k$.

So both $p_1$ and $p_k$ are adjacent only to vertices in $P$.

Since $\deg(p_1) \ge \dfrac n 2$ and $p_1$ cannot be adjacent to itself, $k \ge \dfrac n 2 +1$.


Claim: There is some value of $j$ ($1 \le j \le k$) such that:

  • $p_j$ is adjacent to $p_k$, and
  • $p_{j+1}$ is adjacent to $p_1$.

Suppose that the claim is not true.

Then since all vertices adjacent to $p_1$ or $p_k$ lie on $P$, there must be at least $\deg(p_1)$ vertices on $P$ not adjacent to $p_k$.

Since all the vertices adjacent to $p_k$ and $p_k$ itself also lie on $P$, the path must have at least $\deg(p_1) + \deg(p_k) + 1 \ge n+1$ vertices.

But $G$ has only $n$ vertices: a contradiction.


This gives a cycle $C = p_{j+1} p_{j+2} \ldots p_{k} p_j p_{j-1} \ldots p_2 p_1 p_{j+1}$.

Suppose $G - C$ is nonempty.

Then since $G$ is connected, there must be a vertex $v \in G-C$ adjacent to some $p_i$.

So the path from $v$ to $p_i$ and then around $C$ to the vertex adjacent to $p_i$ is longer than $P$, contradicting the definition of $P$.


Therefore all vertices in $G$ are contained in $C$, making $C$ a Hamilton cycle.

$\blacksquare$


Proof 2

Take any two non-adjacent vertices $u, v \in G$.

Then:

$\displaystyle \deg u + \deg v \ge \frac n 2 + \frac n 2 = n$

The result follows by a direct application of Ore's Theorem.

$\blacksquare$


Source of Name

This entry was named for Gabriel Andrew Dirac.