Bermond's lobster conjecture for lobsters of maximum degree three
Bermond (1979) conjectured that every lobster is graceful. A lobster is a finite tree in which every vertex lies within distance two of a single path. A tree on vertices is graceful if its vertices can be labelled with the distinct integers so that the edge differences are exactly . Is every lobster graceful?
- Result
- Proved(see note)
- Status
- Partial result
- AI contribution
- AI-discovered
- Method
- Computation
- Field
- Graph theory, graceful labelings of trees
- Posed by
- Jean-Claude Bermond, Graceful graphs, radio antennae and French windmills (Graph Theory and Combinatorics, Pitman, 1979)
- Year posed
- 1979
- Years open
- 47y
- Solved
- 2026-11-03
- Model
- GPT-6 Astra (discovery), Codex (formalization)
- Vendor
- OpenAI
- Collaborators
- —
- Verification
- Lean-checked, statement unaudited
- Publication
- Announced
- Significance
- 15 / 100
- Disclosed cost
- —
- Wikipedia
- No dedicated article
What was actually shown
Every finite lobster of maximum degree at most three is graceful: its vertex labels can be taken to be with edge differences exactly . The proof decomposes the lobster along a maximal witnessing path into spine cells and assembles labels from a finite certificate of 6,104 local rules, checked in Lean. The unrestricted lobster conjecture remains open. Related earlier work: Luiz, Campos and Richter (2019) give alpha-labelings for maximum-degree-three lobsters under extra restrictions on legs and endings.
What the AI did
Akram Younso initiated an investigation of the Graceful Tree Conjecture and prompted the agent to continue. The agent identified the subcubic lobster case and produced the argument and certificate. Codex prepared the manuscript and formalized the theorem in Lean.
Verification
No independent mathematician has checked this yet. Read by this site on 15 November 2026 from Zenodo record 23932907 (archive subcubic-lobsters-lean-proof.zip, Lean 4.33.0, mathlib v4.33.0, 10 files, 1,225 lines). The headline theorem Lobster.every_subcubic_lobster_is_graceful was read: for a finite simple graph that is a tree, has maximum degree at most 3 and has a simple path within graph distance 2 of every vertex, it gives a bijection of vertices onto and a bijection of edges onto differences , with on every edge. That matches the conjecture restricted to maximum degree three. A grep found no sorry, admit, axiom or unsafe; three finite checks use native_decide, so the proof trusts Lean's compiler for those evaluations. The rule table has 6,104 rows and its SHA-256 matches the README. Not rebuilt here. The statement is not independently anchored.
Sources
Submitted by LuckyQuokka843 on