Dirac's Theorem
What You'll Learn
You'll learn a powerful sufficient condition that guarantees a graph contains a Hamiltonian cycle—one of the most elegant results in graph theory.
The Core Idea
After learning that finding Hamiltonian cycles is generally difficult, Dirac's Theorem gives us a beautiful shortcut: if every single vertex in a graph has degree at least n/2 (where n ≥ 3 is the total number of vertices), then the graph must have a Hamiltonian cycle.
Think of it this way: if you're at a party with n people and you're friends with at least half the room, and everyone else is also friends with at least half the room, then you can arrange everyone in a circle where each person stands next to people they know. The high degree requirement creates so much connectivity that a cycle visiting every vertex becomes inevitable.
Why This Matters
Dirac's Theorem (1952) transforms the question "Does this graph have a Hamiltonian cycle?" from an intractable problem into a simple degree-checking exercise—when the conditions are met.
Example: Consider a graph with 10 vertices where every vertex has degree at least 5. By Dirac's Theorem, this graph is guaranteed to be Hamiltonian, no searching required!
Note that Dirac's condition is sufficient but not necessary. A graph can be Hamiltonian even if some vertices have degree less than n/2. However, when Dirac's condition holds, you have certainty.
Checking Dirac's Condition
- Count the vertices: n
- Calculate n/2
- Check if every vertex has degree ≥ n/2
- If yes (and n ≥ 3), the graph is Hamiltonian
Key Takeaway: Dirac's Theorem states that if every vertex in a graph on n ≥ 3 vertices has degree at least n/2, the graph is guaranteed to contain a Hamiltonian cycle.