Course contentsShow
← Mathematics
Lesson 2685 of 3,12153. Graph TheoryFree lesson

Dirac's Theorem

If every vertex in a graph on n ≥ 3 vertices has degree ≥ n/2, then the graph is Hamiltonian.

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

  1. Count the vertices: n
  2. Calculate n/2
  3. Check if every vertex has degree ≥ n/2
  4. 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.