Dirac's And Ore's Theorem

Dirac's Theorem

Theorem 1 (Dirac's Theorem): If $G = (V(G), E(G))$ is connected graph on n-vertices so that for every $x, y \in V(G)$, where $x \neq y$, and $\deg (x) + \deg (y) ≥ n$ for all $x, y \in V(G)$, then $G$ is a Hamiltonian graph.

Let's verify Dirac's theorem by testing to see if the following graph is Hamiltonian:

Screen%20Shot%202014-02-19%20at%202.27.35%20PM.png

Clearly the graph is Hamiltonian. However, let's test all pairs of vertices:

$\deg(x) + \deg(y) \geq n$ True/False ?
$\deg(a) + \deg(b) \geq 6$, so $5 + 5 \geq 6$ True
$\deg(a) + \deg(c) \geq 6$, so $5 + 4 \geq 6$ True
$\deg(a) + \deg(d) \geq 6$, so $5 + 5 \geq 6$ True
$\deg(a) + \deg(e) \geq 6$, so $5 + 5 \geq 6$ True
$\deg(a) + \deg(f) \geq 6$, so $5 + 4 \geq 6$ True
$\deg(b) + \deg(c) \geq 6$, so $5 + 4 \geq 6$ True
$\deg(b) + \deg(d) \geq 6$, so $5 + 5 \geq 6$ True
$\deg(b) + \deg(e) \geq 6$, so $5 + 5 \geq 6$ True
$\deg(b) + \deg(f) \geq 6$, so $5 + 4 \geq 6$ True
$\deg(c) + \deg(d) \geq 6$, so $4 + 5 \geq 6$ True
$\deg(c) + \deg(e) \geq 6$, so $4 + 5 \geq 6$ True
$\deg(c) + \deg(f) \geq 6$, so $4 + 4 \geq 6$ True
$\deg(d) + \deg(e) \geq 6$, so $5 + 5 \geq 6$ True
$\deg(d) + \deg(f) \geq 6$, so $5 + 4 \geq 6$ True

So by Dirac's theorem, this graph must be Hamiltonian. We will now look at Ore's theorem.

Ore's Theorem

Ore's theorem is a vast improvement to Dirac's theorem:

Theorem 2 (Ore's Theorem): If $G = (V(G), E(G))$ is connected graph on $n$-vertices where $n \geq 3 $] so that for [[$x, y \in V(G)$, where $x \neq y$, and $\deg (x) + \deg (y) ≥ n$ for each pair of non-adjacent vertices $x$ and $y$ then $G$ is a Hamiltonian graph.

Recall that two vertices are said to be adjacent if they are connected by an edge. Two vertices $x$ and $y$ are said to be adjacent if $\left\{ x, y \right\} \in E(G)$. Thus, non-adjacent vertices $x$ and $y$ are vertices such that $\left\{x, y \right\} \notin E(G)$.

Let's see if this theorem is accurate by testing the graph from earlier, let's call it $G$. This graph is on $6$ vertices and is clearly Hamiltonian. Let's verify this with Ore's theorem. The only pair of non-adjacent vertices are $c$ and $f$, since $\left\{ c, f \right\} \notin E(G)$. For $G$ to be Hamiltonian, it must follow that:

(1)
\begin{align} \deg(c) + \deg(f) \geq 6 \\ 4 + 4 \geq 6 \\ 8 \geq 6 \end{align}

Thus according to Ore's theorem, the graph $G$ is Hamiltonian.

Note that these theorems provide a condition for a graph to always be Hamiltonian. If a graph $G$ does not pass this test, then it doesn't imply that $G$ is not Hamiltonian. However, if the graph $G$ does pass this test, then it is definitely Hamiltonian.

Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License