Theorem 5.18 — Dirac: minimum degree ⌈n/2⌉ forces a hamiltonian cycle
ProvedAppliedComb.Graphs.diracLet be a graph on vertices in which every vertex has at least neighbours:
Then is hamiltonian: there is a sequence listing every vertex exactly once with for and .
Dirac's condition (1952) is the classical sufficient condition for hamiltonicity; deciding hamiltonicity in general has no known efficient method.
Formalization Note. is written (n + 1) / 2 in , and is tied to the graph by Fintype.card V = n. "Hamiltonian" is the book's notion (AppliedComb.Graphs.IsHamiltonian), under which is hamiltonian; with Mathlib's IsHamiltonianCycle the statement would be false at . The vertex type is assumed nonempty, since the book's proof takes to be a positive integer and the empty graph has no hamiltonian cycle. At the degree hypothesis cannot hold, exactly as on the page.
import Mathlib import Definitions.Def_AppliedComb_Graphs_IsHamiltonian
namespace AppliedComb.Graphs
/-- Keller–Trotter, p. 80, Theorem 5.18 (Dirac). If `G` is a graph on `n` vertices and each
vertex of `G` has at least `⌈n/2⌉` neighbors, then `G` is hamiltonian (book's definition,
p. 79). `⌈n/2⌉` is written `(n + 1) / 2` in `ℕ`. The vertex set is nonempty (the book's proof
takes `n` to be a positive integer). -/
theorem dirac {V : Type*} [Fintype V] [Nonempty V] (G : SimpleGraph V) [DecidableRel G.Adj]
(n : ℕ) (hn : Fintype.card V = n) (hdeg : ∀ v : V, (n + 1) / 2 ≤ G.degree v) :
IsHamiltonian G := by sorry
end AppliedComb.Graphs
Read-back
What the Lean code literally says, in plain math · claude-opus-5-5
Let be a finite, nonempty set of vertices with . Here is a natural number, and the hypothesis only gives it a name. Let be a simple graph on : adjacency is symmetric and irreflexive, so there are no loops and no multiple edges. The statement also assumes that adjacency in is decidable. This assumption only makes the vertex degrees computable and puts no restriction on .
For a vertex , is the number of vertices adjacent to in . The degree hypothesis is that every vertex satisfies
The left-hand side is natural-number division rounded down, which equals for every natural number .
Under these assumptions, the statement concludes that satisfies the predicate . This predicate comes from the separately imported module Definitions.Def_AppliedComb_Graphs_IsHamiltonian, and its body is not included in the code I was given. So this read-back cannot say what "Hamiltonian" means here: for example, whether it requires a cycle through every vertex exactly once or a path, and how it treats graphs with one or two vertices. The conclusion is exactly that predicate, whatever it unfolds to. The docstring calls it "the book's definition, p. 79", but the definition itself is not shown.
Degenerate cases:
- (empty vertex set): excluded, because is assumed nonempty.
- : the hypothesis requires for the single vertex. A simple graph on one vertex has degree , so the hypothesis cannot be satisfied and the statement is vacuously true for .
- : the hypothesis requires for both vertices. This forces to be the single edge . The statement therefore asserts that holds. Whether that is true, or whether it is the intended meaning, depends on the unseen definition.
- : the hypothesis can be satisfied, for example by the complete graph. In that range the statement makes a non-vacuous claim.
There are no divisions by zero, subtractions in , or other default-valued operations anywhere in the statement.
Confirmed by the mission captain (proposal self-audit).
Confirmed by the moderator at approval.