Bermond's lobster conjecture asserts that every lobster graph admits a graceful labeling (Bermond
1979). For a tree with edges, this means assigning
the labels 0 through bijectively to the vertices
so that the absolute differences of the labels
at the ends of the edges are precisely the distinct
integers 1 through .
The conjecture is a special case of the graceful tree conjecture. It extends the known gracefulness of caterpillar
graphs to trees with all vertices
at graph distance at most 2 from a common graph
path (Gallian 2026). Morgan (2002) proved the case of lobster
graphs with a perfect matching. Younso (2026)
reports an AI-developed computer-assisted proof for lobster
graphs of maximum vertex degree at most 3. The
certificate uses compiled evaluation for three finite checks and the result has not
been independently peer reviewed. The unrestricted conjecture remains open.
Bermond, J. C. "Graceful Graphs, Radio Antennae and French Windmills." In Graph Theory and Combinatorics (Ed. R. J.
Wilson). London, England: Pitman, pp. 18-37, 1979.Gallian, J. A.
"A Dynamic Survey of Graph Labeling." Elec. J. Combin., Dynamic
Survey DS6, Nov. 6, 2026. https://doi.org/10.37236/27.Morgan,
D. "All Lobsters with Perfect Matchings Are Graceful." Elec. Notes Disc.
Math.11, 503-508, 2002. https://doi.org/10.1016/S1571-0653(04)00095-2.Younso,
A. "A Finite Certificate for Graceful Labelings of Subcubic Lobsters."
Software and Lean sources. Nov. 3, 2026. https://doi.org/10.5281/zenodo.23932907.