📂Graph Theory

Proof of Dirac's Theorem in Graph Theory

Theorem ¹

Let’s suppose that $G$ is a simple graph with $n ( \ge 3)$ vertices.

• [1] Dirac’s Theorem: If every vertex $v$ of $G$ satisfies $\deg (v) \ge n / 2$, then $G$ is a Hamiltonian graph.
• [2] Ore’s Theorem: If for every pair of non-adjacent vertices $(v ,w)$ of $G$, $\deg (v) + \deg(w) \ge n$ is satisfied, then $G$ is a Hamiltonian graph.

Explanation

Dirac’s Theorem identifies conditions under which a graph is sufficiently to be a Hamiltonian graph, though not necessarily equivalent. This was proven in 1952 and later generalized by Ore in 1960. However, Dirac’s Theorem maintained its standing, relegating Ore’s Theorem to a corollary.

Proof

Strategy: It is trivial that Ore’s theorem implies Dirac’s theorem, so proving Ore’s theorem is sufficient. By contradiction, we add $m$ edges to $G$ to demonstrate it is still Hamiltonian, and using mathematical induction, adding just $m , m -1 , \cdots , 1 , 0$ more edges still results in a Hamiltonian graph, leading to the conclusion that $G$ is Hamiltonian.

[2]

Suppose $\deg (v) + \deg(w) \ge n$ but $G$ is not a Hamiltonian graph. $$ v_{1} \to \cdots \to v_{n} $$ For $n$ vertices $v_{1} , \cdots , v_{n} \in V(G)$, adding some edges to the graph $H$ should enable a path that goes through all vertices as above. Assuming only an edge connecting $v_{1}$ and $v_{n}$ is missing, making it not a cycle and consequently, $H$ not a Hamiltonian graph either. Of course, this addition of edges to $H$ does not contravene $$\deg (v) + \deg(w) \ge n$$ since it only increases the degree. Also, since $v_{1}$ and $v_{n}$ are not adjacent, $$\deg (v_{1}) + \deg(v_{n}) \ge n$$ This means that the sum of degrees of $v_{1}$ and $v_{n}$ is greater than the total vertices, implying there exists a natural number $2 \le i \le n$ such that $v_{1}$ is adjacent to $v_{i}$ while $v_{n}$ is adjacent to $v_{i-1}$. Consequently, a cycle like the following must exist: $$ v_{1} \to v_{2} \to \cdots \to v_{i-1} \to v_{n} \to v_{n-1} \to \cdots \to v_{i+1} \to v_{i} \to v_{1} $$ This contradicts the assertion that $H$ is not a Hamiltonian graph. The same reasoning applies to a new graph $h '$ created by removing an edge included in the Hamiltonian cycle of $H$ but added to $G$, resulting in a contradiction to the assumption that $G$ is not a Hamiltonian graph.

■