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