Graceful Tree Conjecture
Status partial high confidence
The Graceful Tree Conjecture remains open. The strongest progress since the OPG posting (2007) is asymptotic: Adamaszek, Allen, Grosu and Hladky (2016, arXiv:1608.01577) proved that almost all trees admit an 'almost graceful' labelling using vertex labels in $\{1,\dots,(1+c)n\}$, and Letzter, Pokrovskiy and Williams (2025, arXiv:2511.11331) showed that every sufficiently large tree on $n$ vertices has gracesize $\ge (1-\varepsilon)n$, i.e. an asymptotic version of the conjecture. A claimed full proof by Gnang (arXiv:2202.03178, 2022) is an unpublished preprint flagged by arXiv for text overlap and has not been verified by the community.
Cited literature (3)
-
Proves a relaxation of the conjecture: for any $c>0$, asymptotically almost all $n$-vertex trees admit an injective labelling into $\{1,\dots,(1+c)n\}$ with pairwise distinct edge differences (and all bounded-degree trees do).
-
Proves an asymptotic version of the Graceful Tree Conjecture: for every $\varepsilon>0$, every sufficiently large tree on $n$ vertices admits a labelling whose gracesize is at least $(1-\varepsilon)n$, i.e. all but $\varepsilon n$ edge differences are distinct.
-
Claims a complete proof of the Graceful Tree Conjecture via a functional reformulation and a composition lemma; remains an unpublished preprint, has been flagged by arXiv for text overlap with arXiv:2111.12812, and is not accepted by the community as a verified proof.
Reviewer notes. Gallian's Dynamic Survey of Graph Labeling (DS6, version dated October 30, 2025) continues to list the Graceful Tree Conjecture as open. The Gnang preprint (arXiv:2202.03178) is included with kind 'proof' for completeness but should be regarded with scepticism: it has been on arXiv since 2022 with no journal publication, and arXiv flagged it for text overlap with another preprint. The status 'partial' reflects the verified asymptotic progress (Adamaszek et al. 2016, Letzter-Pokrovskiy-Williams 2025); the original conjecture that every tree is graceful is still open.
Discussion
Label the vertices of a simple undirected graph $ G(V,E) $ (where $ |V| = n $ and $ |E| = m $ ) with integers from $ 0 $ to $ m $ . Now label each edge with absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labelled $ 1 $ through $ m $ inclusive (with no number repeated). A graph is called graceful if it has at least one such labeling. This labeling was originally introduced in 1967 by Rosa. The name graceful labeling was coined later by Golomb. Gracefully labeled graphs serve as models in a wide range of applications including coding theory and communication network addressing. The graceful labeling problem is to determine which graphs are graceful. It is conjectured (by Kotzig, Ringel and Rosa) that all trees are graceful. Despite numerous (more than 200) publications on graceful labeling for over three decades, only a very restricted classes of trees (and also of some other graphs) have been shown to be graceful. These restricted classes include paths, stars, complete bipartite graphs, prism graphs, wheel graphs, caterpillar graphs, olive trees, and symmetrical trees.