Papex

Open problem · Mathematics · Open

Graceful tree conjecture

Can the vertices of every tree with m edges be labelled with distinct numbers from 0 to m so that the edge differences are exactly 1 to m?

Summary

Also called the Ringel–Kotzig conjecture, it has been confirmed for many families of trees and by computer searches over small trees, but no proof covers every tree.

Why it is open

A tree is a connected graph with no cycles, and a tree with m edges has m + 1 vertices [5]. A graceful labelling assigns the numbers 0 to m to these vertices, one each, so that the absolute differences of the labels across the edges are all distinct; they are then exactly 1 to m [5, 8]. A. Rosa introduced such labellings in 1967 under the name β-valuations, and S. W. Golomb later called them graceful [6]. Joseph Gallian's survey calls the statement that every tree is graceful the Ringel–Kotzig conjecture, while other authors credit Rosa [5, 6, 8].

The conjecture grew out of a question about decompositions. In 1963 G. Ringel conjectured that the complete graph on 2n + 1 vertices, in which every pair of vertices is joined, splits into 2n + 1 copies of any tree with n edges, and Rosa introduced β-valuations as a way to attack it [5, 6]. A graceful labelling gives such a split directly, so the graceful tree conjecture implies Ringel's [5].

A resolution would be a graceful labelling for every tree, or a tree that has none. No prize body sets conditions; the status on this page follows Wikipedia's list of unsolved problems in mathematics [9]. Gallian records that A. Kotzig called the effort to prove the conjecture a "disease" [6]. He quotes M. Alfalayleh and colleagues, "The faith in the conjecture is so strong that if a tree without a graceful labeling were indeed found, then it probably would not be considered a tree", and also reports that A. Vietri "expresses doubts about the validity of the graceful tree conjecture" [6].

What is known

Families of graceful trees (1967–2025). Gallian's survey lists, among the trees known to be graceful, caterpillars (trees that become a path when their leaves are removed), trees with at most four leaves, trees of diameter at most 5 (the last case in 2001), symmetrical trees, olive trees, banana trees, and spiders, trees with at most one vertex of degree above 2, whose legs differ in length by at most one [6]. J. C. Bermond conjectured in 1979 that lobsters, trees that become a caterpillar when their leaves are removed, are graceful; this is proved for lobsters with a perfect matching or an almost perfect matching, and for further classes [6]. For trees of diameter 6 the survey lists results for some classes [6]. Gallian writes that the conjecture "remains open even for trees with maximum degree 3" [6].

Computer searches (to 2010). According to Wenjie Fang, R. E. L. Aldred and Brendan McKay verified the conjecture for all trees with at most 27 vertices using a stochastic local search, and M. Horton, in a dissertation, for at most 29 [1]. In a 2010 preprint, not peer reviewed, Fang combined a deterministic backtracking search with a probabilistic one and reported that every tree with at most 35 vertices is graceful; the 2,262,366,343,746 trees with 35 vertices were processed with the help of volunteer computing [1]. Gallian's survey records the same result [6].

Approximate versions (1995–2026). The gracesize of an n-vertex tree is the largest number of distinct edge differences over all labellings with 1 to n, so the conjecture says that it is always n − 1 [8]. Shoham Letzter, Alexey Pokrovskiy and Ella Williams cite a 1995 result of Rosa and J. Širáň that it is at least 5(n − 1)/7 [8]. In 2020 Anna Adamaszek, Peter Allen, Codruţ Grosu and Jan Hladký showed that for every γ > 0 and all large n, a tree whose maximum degree is bounded by a constant times n/log n has a labelling with distinct differences that uses labels from 1 to ⌈(1 + γ)n⌉; asymptotically almost all trees qualify [3]. Richard Montgomery, Pokrovskiy and Benny Sudakov proved an asymptotic version of Ringel's conjecture, described below, and showed that all trees have an almost-harmonious labelling, a relaxation of a different labelling conjecture of Graham and Sloane [4]. In a 2025 preprint, not peer reviewed and revised in July 2026, Letzter, Pokrovskiy and Williams prove that for every ε > 0, every large enough n-vertex tree has gracesize at least (1 − ε)n [8].

Ringel's conjecture (1963–2025). Kotzig proposed a stronger form of Ringel's conjecture [8]. Colour each edge ij of the complete graph on the vertices 0 to 2n by the k between 1 and n for which i − j is k or −k modulo 2n + 1; Kotzig conjectured that every tree with n edges then has a rainbow copy, one whose edges all have different colours [5]. Shifting such a copy 2n + 1 times splits the complete graph, and a graceful labelling is exactly a rainbow copy that uses the vertices 0 to n [5]. Felix Joos, Jaehoon Kim, Daniela Kühn and Deryk Osthus proved Ringel's conjecture for bounded-degree trees [2], which Montgomery and colleagues describe as very large bounded-degree trees [5]. In a preprint of January 2020, published in 2021, Montgomery, Pokrovskiy and Sudakov proved Ringel's conjecture for every sufficiently large n, by finding rainbow copies of every n-edge tree [5]. Peter Keevash and Katherine Staden independently proved, in a preprint of April 2020 published in 2025, that any quasirandom graph (one whose edges are spread like those of a random graph) with n vertices and rn edges splits into n copies of any fixed tree with r edges; the case of the complete graph gives Ringel's conjecture for large n [6, 7]. Letzter and colleagues note that these results prove Ringel's conjecture and Kotzig's stronger form for all large n [8]. Wikipedia's list places Ringel's conjecture among problems solved since 2015 [9]. The graceful tree conjecture is not covered: fixing the vertex set as 0 to n "adds an additional restriction which makes it harder" to find the rainbow copy, Montgomery and colleagues write [5].

Main approaches

Labelling families of trees. Find graceful labellings for one class of trees at a time, or combine graceful trees into larger ones [6]. Strongest evidence: the long list of graceful families, including every tree of diameter at most 5 [6]. Main difficulty: the conjecture is open even for maximum degree 3, and Gallian notes that labelling papers "focus on particular classes of graphs and methods, and feature ad hoc arguments" [6].

Exhaustive computation. Find a graceful labelling for every tree up to a given size [1]. Strongest evidence: every tree with at most 35 vertices [1]. Main difficulty: the number of trees grows from 823,065 with 20 vertices to 2,262,366,343,746 with 35, and Fang estimated by extrapolation that the 35-vertex case alone would take 7.7 years on one processor core [1].

Relaxed labellings. Allow a few extra labels or a few repeated differences, and find such labellings with randomised or rainbow-embedding methods [3, 8]. Strongest evidence: the 2025 gracesize bound for all large trees [8] and the range-relaxed labellings of Adamaszek and colleagues [3]. Main difficulty: the second needs the degree bound [3], and Letzter and colleagues see "no obvious argument" that a large gracesize gives a labelling with few extra labels [8]; neither gives an exact graceful labelling.

Decompositions instead of labellings. Prove Ringel's and Kotzig's conjectures directly, by finding rainbow copies of trees or by decomposing quasirandom graphs [5, 7]. Strongest evidence: both are proved for all large n [5, 7, 8]. Main difficulty: a graceful labelling is a rainbow copy on exactly the vertices 0 to n, a restriction that Montgomery and colleagues say makes the copy harder to find [5].

Open sub-questions

  1. Diameter 6. Every tree of diameter at most 5 is graceful, and for diameter 6 only some classes are covered [6]. Is every tree of diameter 6 graceful?
  2. Lobsters. Is every lobster graceful, as Bermond conjectured in 1979, including lobsters without an almost perfect matching [6]?
  3. Spiders with six legs. Gallian's survey reports graceful labellings for spiders with at most five legs and for spiders whose legs differ by at most one [6]. Is every spider with six legs graceful?
  4. Few extra labels for every tree. Does every n-vertex tree, with no bound on its maximum degree, have a labelling with distinct differences using labels from 1 to (1 + o(1))n, the next step that Letzter, Pokrovskiy and Williams propose [3, 8]?
  5. Trees with few graceful labellings. Among trees with n vertices, does the tree with the fewest graceful labellings always lie in the two caterpillar families that D. Anick's counts point to [6]?

Work on this in Papex

If you have a testable answer to one of the sub-questions above, you can draft it as a private hypothesis in Papex, or prepare the draft from Claude or ChatGPT with the Papex connector. You review the exact version, sign it and decide whether to publish it; a public record that names this problem is listed on this page. A Papex record shows who signed which version and when. It is not peer review and does not mean the hypothesis is correct.

Key references

  1. Fang, W. (2010). A computational approach to the graceful tree conjecture. Preprint, arXiv:1003.3045 (version 2, 19 August 2010), not peer reviewed. Source · Checked 16 Oct 2026
  2. Joos, F., Kim, J., Kühn, D. & Osthus, D. (2019). Optimal packings of bounded degree trees. Journal of the European Mathematical Society 21(12), 3573–3647. 10.4171/jems/909 · Checked 16 Oct 2026
  3. Adamaszek, A., Allen, P., Grosu, C. & Hladký, J. (2020). Almost all trees are almost graceful. Random Structures & Algorithms 56(4), 948–987. 10.1002/rsa.20906 · Checked 16 Oct 2026
  4. Montgomery, R., Pokrovskiy, A. & Sudakov, B. (2020). Embedding rainbow trees with applications to graph labelling and decomposition. Journal of the European Mathematical Society 22(10), 3101–3132. 10.4171/JEMS/982 · Checked 16 Oct 2026
  5. Montgomery, R., Pokrovskiy, A. & Sudakov, B. (2021). A proof of Ringel's conjecture. Geometric and Functional Analysis 31(3), 663–720. 10.1007/s00039-021-00576-2 · Checked 16 Oct 2026
  6. Gallian, J. A. (2025). A dynamic survey of graph labeling, twenty-eighth edition (30 October 2025). The Electronic Journal of Combinatorics, Dynamic Survey DS6. 10.37236/27 · Checked 16 Oct 2026
  7. Keevash, P. & Staden, K. (2025). Ringel's tree packing conjecture in quasirandom graphs. Journal of the European Mathematical Society 27(5), 1769–1826. 10.4171/jems/1604 · Checked 16 Oct 2026
  8. Letzter, S., Pokrovskiy, A. & Williams, E. (2025). On the gracesize of trees. Preprint, arXiv:2511.11331 (version 2, 31 July 2026), not peer reviewed. Source · Checked 16 Oct 2026
  9. Wikipedia. List of unsolved problems in mathematics (revision of 15 October 2026). Source · Checked 16 Oct 2026

Page reviewed 16 Oct 2026

Source

Open, as listed by Wikipedia · Unsolved problems in mathematics. Checked 08 Oct 2026.

The status is the source’s. Papex does not decide whether a problem is solved.

Records on this problem

No public record addresses this problem yet.

More in Mathematics