Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Formalpedia

Theorem 5.18 — Dirac: minimum degree ⌈n/2⌉ forces a hamiltonian cycle

Proved
AppliedComb.Graphs.dirac

by mikedeng1 · Sep 28, 2026 · Mathlib 0df444a (Lean v4.33.1)

combinatoricsgraph-theoryhamiltonianp2o-batch-books5p2o-gran-per-chapterp2o-plan-bookp2o-v1

Let G=(V,E)G = (V, E)G=(V,E) be a graph on n=∣V∣≥1n = |V| \ge 1n=∣V∣≥1 vertices in which every vertex has at least ⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉ neighbours:

deg⁡G(v)≥⌈n2⌉for every v∈V.\deg_G(v) \ge \left\lceil \tfrac{n}{2} \right\rceil \quad \text{for every } v \in V.degG​(v)≥⌈2n​⌉for every v∈V.

Then GGG is hamiltonian: there is a sequence (x1,…,xn)(x_1, \dots, x_n)(x1​,…,xn​) listing every vertex exactly once with xixi+1∈Ex_i x_{i+1} \in Exi​xi+1​∈E for i<ni < ni<n and x1xn∈Ex_1 x_n \in Ex1​xn​∈E.

Dirac's condition (1952) is the classical sufficient condition for hamiltonicity; deciding hamiltonicity in general has no known efficient method.

Formalization Note. ⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉ is written (n + 1) / 2 in N\mathbb NN, and nnn is tied to the graph by Fintype.card V = n. "Hamiltonian" is the book's notion (AppliedComb.Graphs.IsHamiltonian), under which K2K_2K2​ is hamiltonian; with Mathlib's IsHamiltonianCycle the statement would be false at n=2n = 2n=2. The vertex type is assumed nonempty, since the book's proof takes nnn to be a positive integer and the empty graph has no hamiltonian cycle. At n=1n = 1n=1 the degree hypothesis cannot hold, exactly as on the page.

Preamble
import Mathlib
import Definitions.Def_AppliedComb_Graphs_IsHamiltonian
Formal statement
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
Source
Keller & Trotter, Applied Combinatorics (2017 Edition), p. 80, Theorem 5.18 (definition of hamiltonian on p. 79)
Read-back

What the Lean code literally says, in plain math · claude-opus-5-5

Let VVV be a finite, nonempty set of vertices with ∣V∣=n|V| = n∣V∣=n. Here nnn is a natural number, and the hypothesis card(V)=n\mathrm{card}(V) = ncard(V)=n only gives it a name. Let GGG be a simple graph on VVV: adjacency is symmetric and irreflexive, so there are no loops and no multiple edges. The statement also assumes that adjacency in GGG is decidable. This assumption only makes the vertex degrees computable and puts no restriction on GGG.

For a vertex vvv, deg⁡G(v)\deg_G(v)degG​(v) is the number of vertices adjacent to vvv in GGG. The degree hypothesis is that every vertex satisfies

⌊n+12⌋  ≤  deg⁡G(v).\left\lfloor \frac{n+1}{2} \right\rfloor \;\le\; \deg_G(v).⌊2n+1​⌋≤degG​(v).

The left-hand side is natural-number division rounded down, which equals ⌈n/2⌉\lceil n/2 \rceil⌈n/2⌉ for every natural number nnn.

Under these assumptions, the statement concludes that GGG satisfies the predicate IsHamiltonian(G)\mathrm{IsHamiltonian}(G)IsHamiltonian(G). 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:

  • n=0n = 0n=0 (empty vertex set): excluded, because VVV is assumed nonempty.
  • n=1n = 1n=1: the hypothesis requires ⌊2/2⌋=1≤deg⁡G(v)\lfloor 2/2 \rfloor = 1 \le \deg_G(v)⌊2/2⌋=1≤degG​(v) for the single vertex. A simple graph on one vertex has degree 000, so the hypothesis cannot be satisfied and the statement is vacuously true for n=1n = 1n=1.
  • n=2n = 2n=2: the hypothesis requires deg⁡G(v)≥1\deg_G(v) \ge 1degG​(v)≥1 for both vertices. This forces GGG to be the single edge K2K_2K2​. The statement therefore asserts that IsHamiltonian(K2)\mathrm{IsHamiltonian}(K_2)IsHamiltonian(K2​) holds. Whether that is true, or whether it is the intended meaning, depends on the unseen definition.
  • n≥3n \ge 3n≥3: 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 N\mathbb{N}N, or other default-valued operations anywhere in the statement.

Human review
  • Endorsed by Shuze Chen · Oct 2, 2026

    Confirmed by the moderator at approval.

  • Endorsed by mikedeng1 · Oct 2, 2026

    Confirmed by the mission captain (proposal self-audit).

View graph

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me