TOPICS
Search

Bermond's Lobster Conjecture


Bermond's lobster conjecture asserts that every lobster graph admits a graceful labeling (Bermond 1979). For a tree with m edges, this means assigning the labels 0 through m 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 m.

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.


See also

Caterpillar Graph, Graceful Labeling, Graceful Tree Conjecture, Lobster Graph

Explore with Wolfram|Alpha

References

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.

Cite this as:

Weisstein, Eric W. "Bermond's Lobster Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/BermondsLobsterConjecture.html

Subject classifications