Open problem, Combinatorics and discrete mathematics, posed 1967

Graceful tree conjecture

Open

Every finite tree $T = (V, E)$ with $m = |V| - 1$ edges admits a graceful labeling: an injective map $f: V \to \{0, 1, \dots, m\}$ such that the induced edge weights $|f(u) - f(v)|$ for $uv \in E$ are all distinct and therefore equal to $\{1, 2, \dots, m\}$ .

Research frontier as of 2026

As of 2026, the graceful tree conjecture remains open in general. It is verified for all trees on $n \le 35$ vertices and proved for structured families such as paths, caterpillars, symmetrical trees, olive trees, spider trees, and trees of diameter at most $5$ . For arbitrary large trees, probabilistic and absorption methods have proved asymptotic relaxations—showing that an $m$ -edge tree can be gracefully labeled using labels from $\{0, 1, \dots, (1 + o(1))m\}$ or embedded as a rainbow tree in $K_{2m+1}$ —but eliminating the $o(m)$ slack in the label range remains beyond current techniques.

Best known results

Every tree on $n \le 35$ vertices is graceful, verified by exhaustive computer search (Aldred–McKay 1998 for $n \le 27$ ; Fang 2010 for $n \le 35$ ).
Paths, caterpillars, trees with at most $4$ leaves, trees of diameter at most $5$ , olive trees, and symmetrical trees are proved to be graceful for all sizes.
Ringel's decomposition conjecture holds for all sufficiently large trees $T$ with $m$ edges (Montgomery, Pokrovskiy, and Sudakov, 2020/2021), and bounded-degree trees admit asymptotic graceful labelings into $\{0, 1, \dots, (1 + o(1))m\}$ .

Tools and where they stop

Tool	Achieved	Where it stops
Inductive $\alpha$ -valuations and tree amalgamation	Constructs explicit graceful labelings for caterpillars, lobsters of restricted form, olive trees, and trees of diameter at most $5$ by shifting and gluing bipartitioned label ranges.	Not all trees admit $\alpha$ -valuations (for example, certain trees with vertices of degree $3$ ), and irregular branching destroys the contiguous interval structure needed for inductive gluing.
Rainbow subgraphs and distributive absorption (Montgomery–Pokrovskiy–Sudakov)	Embeds any sufficiently large $m$ -edge tree as a rainbow subgraph of $K_{2m+1}$ under the cyclic distance coloring, completely resolving Ringel's conjecture for large $m$ .	Cyclic distance in $\mathbb{Z}_{2m+1}$ wraps around modulo $2m+1$ , whereas a graceful labeling requires exact absolute differences in $\{0, 1, \dots, m\}$ without wrap-around.

Open questions

Is every lobster tree (a tree in which removing all leaves and their incident paths of length at most $1$ leaves a path, conjectured graceful by Bermond in 1979) graceful?
Does every sufficiently large bounded-degree tree $T$ with $m$ edges admit an exact graceful labeling into $\{0, 1, \dots, m\}$ ?

References

Alexander Rosa (1967). On certain valuations of the vertices of a graph
Joseph A. Gallian (2022). A dynamic survey of graph labeling
Richard Montgomery, Alexey Pokrovskiy, Benny Sudakov (2021). A proof of Ringel's conjecture · DOI:10.1007/s00039-021-00576-2 · arXiv:2001.02665