# 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](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/GracefulLabeling.lean), or of the case of paths and caterpillars.

## References

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

## Source

Imported from [Formal Conjectures Wikipedia/GracefulLabeling](https://github.com/google-deepmind/formal-conjectures/blob/main/FormalConjectures/Wikipedia/GracefulLabeling.lean), 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.