Graph Theory → Hamiltonian

Dirac's Theorem

Let \(G\) be a simple graph with \(n \ge 3\) vertices. If every vertex satisfies \( \deg(v) \ge \frac{n}{2} \), then \(G\) has a Hamiltonian cycle.

\text{If } \deg(v) \ge \frac{n}{2} \text{ for all } v \in V, \text{ then } G \text{ is Hamiltonian.}

Intuition: if each vertex is connected to at least half of the graph, there is enough connectivity to “stitch together” a cycle passing through all vertices.

Important: This is a sufficient condition, not a necessary one. A graph may be Hamiltonian even if it does not satisfy this inequality.

Ore's Theorem

Let \(G\) be a simple graph with \(n \ge 3\) vertices. If, for every pair of non-adjacent vertices \(u\) and \(v\), we have \( \deg(u) + \deg(v) \ge n \),
then \(G\) has a Hamiltonian cycle.

\begin{aligned} \text{If } \deg(u) + \deg(v) \ge n &\text{ for every non-adjacent pair } (u,v), \\ &\text{ then } G \text{ is Hamiltonian.} \end{aligned}

Intuition: even if two vertices are not directly connected, the sum of their degrees guarantees sufficient connectivity in the rest of the graph.

Ore's Theorem generalizes Dirac's Theorem. If Dirac’s condition is satisfied, then Ore’s condition is also satisfied.

Discrete Mathsfor Engineers

Dirac's Theorem

Ore's Theorem