Graceful tree conjecture

A tree is a connected pattern of dots and lines with no loop: between two dots there is only one route. Give every dot a different number, using 1 through the number of dots, and write the positive difference on each line. For four dots in a row, use the labels 1, 4, 2, 3 in that order. Their line differences are 3, 2, 1, using every required difference once. The graceful tree conjecture asks whether every finite tree, whatever its branching shape, can be numbered this way.[1]

The question is whether the shape of any finite tree can be reconciled with a complete range of distinct edge differences. A tree is a connected graph without cycles. For a tree $T$ with $n$ vertices and $n-1$ edges, assign each vertex a different label from $1,\ldots,n$, using every label once. Write $f(u)$ for the label at vertex $u$, and $E(T)$ for the set of connected vertex pairs, or edges. Gracefulness requires $$\{\lvert f(u)-f(v)\rvert:uv\in E(T)\}=\{1,\ldots,n-1\}.$$ The left side takes the positive difference at every connected pair. Since there are exactly $n-1$ edges, the equality requires every difference once. Subtracting 1 from every label gives the equivalent convention $0,\ldots,n-1$. On a four-vertex path, 1,4,2,3 works; 1,2,3,4 produces three copies of difference 1 and fails. That failed numbering is not a counterexample to the conjecture, because the same path has a successful numbering.[1]

It works for many kinds of trees. Results allowing a few repeated or missing differences do not prove the exact rule for all trees.[1]

The November 2025 preprint, revised in July 2026, proves an asymptotic weakening. Having nearly all distinct differences is insufficient for the exact all-trees statement.[1]

The labels coordinate the whole tree: changing one dot’s number changes every difference on a line attached to it. This packing of distinct differences also has a wider use. A gracefully labeled tree can be shifted through a larger network with a connection between every pair, producing copies of the tree that cover all those connections without overlap.[1]

The connection to graph decomposition gives the differences a purpose. If a tree with $m$ edges is graceful, label its vertices within $0,\ldots,m$, place them among $2m+1$ vertices arranged cyclically, and shift all labels together around that cycle. The $2m+1$ shifted copies partition the edges of the complete graph $K_{2m+1}$: each pairwise connection appears once. For the four-vertex path, the equivalent labels 0,3,1,2 give seven shifted paths covering the 21 edges of $K_7$. Gracefulness supplies this construction; proving a broader decomposition theorem by another method does not necessarily provide graceful labels for the original tree.[1]