The graceful tree conjecture

Label the vertices of a tree with $m$ edges by distinct numbers from $\{0, 1, \dots, m\}$. The labelling is graceful if the differences across the edges are exactly $1, 2, \dots, m$, each once. Ringel and Kotzig conjectured in the 1960s that every tree has a graceful labelling. Computers have confirmed it for all trees with up to 35 vertices, and an asymptotic version is now known for all large trees, but the conjecture is open.

Problem

Let $T$ be a tree with $m$ edges. A graceful labelling of $T$ is an injective map $f$ from the vertices of $T$ to $\{0, 1, \dots, m\}$ such that the edge labels $|f(u) - f(v)|$, over the edges $uv$ of $T$, are exactly the numbers $1, 2, \dots, m$.

Conjecture (Ringel–Kotzig). Every tree has a graceful labelling.

Background

The conjecture arose from Ringel's 1963 question about decomposing complete graphs into copies of a tree, and is attributed to Ringel and Kotzig. Rosa (1967) introduced these labellings, which he called β-valuations; a graceful labelling of a tree with $m$ edges yields a cyclic decomposition of the complete graph $K_{2m+1}$ into $2m+1$ copies of the tree. Graceful labellings have since become a large topic in graph labelling.

What is known

• Paths and caterpillars are graceful (Rosa, 1967), as are many other families.
• All trees with at most 27 vertices are graceful (Aldred and McKay, 1998); computations by Fang (2010) extend this to all trees with at most 35 vertices.
• Adamaszek, Allen, Grosu and Hladký (2020) proved an approximate version: for every $c > 0$ and large $n$, every tree on $n$ vertices with maximum degree $O(n/\log n)$ has an injective labelling from $\{1, \dots, (1+c)n\}$ with distinct edge differences.
• Letzter, Pokrovskiy and Williams (2025, revised 2026; preprint) proved that for every $\varepsilon > 0$ and large $n$, every tree on $n$ vertices has a bijective labelling by $\{1, \dots, n\}$ with at least $(1 - \varepsilon)n$ distinct edge differences.
• A claimed proof of the full conjecture (Chalise, Clark and Gnang, arXiv:2409.01981) was withdrawn in 2026.
• Ringel's original decomposition conjecture was proved for large $n$ by Montgomery, Pokrovskiy and Sudakov (2021), by different methods; it does not imply the graceful tree conjecture.

What would count as progress

• A graceful labelling for every tree in a new infinite family, with a proof, or extended computer verification beyond 35 vertices. Each labelling is checkable instantly, so certificates can be published.
• A counterexample: a tree with no graceful labelling. For a given tree this is a finite search, though a large one.
• Quantitative versions of the asymptotic results, for example at least $n - f(n)$ distinct edge differences with an explicit $f(n) = o(n)$.
• A formal proof of the Lean statement graceful_tree_conjecture in Wikipedia/GracefulLabeling.lean, or of the case of paths and caterpillars.

References

1. W. Fang, A computational approach to the graceful tree conjecture, arXiv:1003.3045 (2010).
2. A. Adamaszek, P. Allen, C. Grosu and J. Hladký, Almost all trees are almost graceful, Random Structures Algorithms 56 (2020), 948–987.
3. S. Letzter, A. Pokrovskiy and E. Williams, On the gracesize of trees, arXiv:2511.11331 (2025).
4. R. Montgomery, A. Pokrovskiy and B. Sudakov, A proof of Ringel's conjecture, Geom. Funct. Anal. 31 (2021), 663–720; arXiv:2001.02665.

Source

Imported from Formal Conjectures Wikipedia/GracefulLabeling, curated by Google DeepMind and contributors. Open according to the source as of 2026-10-20. The statement above is written in our own words; see the source for the original wording, history and discussion.