The graceful tree theorem, also known as the graceful tree conjecture, is the conjecture that every tree is graceful. Kotzig proposed the conjecture in 1965 (Bondy and Murty 1976; Knuth 2025, p. 24). Many authors have tried to prove it. Despite Knuth's observation that "the GTC is almost certainly true" (Knuth 2025, p. 24), no proof or refutation has been discovered to date.
Since a tree on 
vertices has 
graph edges, all values
0 to 
appear in any graceful labeling of its vertices.
As a result, the label 
of a graph edge can occur only
when that graph edge is incident on vertices
with labels 0 and 
,
meaning labels 0 and 
must occur at adjacent vertices
in a graceful labeling (Horton 2003, p. 7).
Nikoloski et al. (2002) found an algorithm that
uses a triangular tableau to identify and ignore cases of this type (Horton 2003,
p. 7).
Bounds on the number of vertices 
up to which the conjecture
has been computationally verified are summarized in the following table.
 | reference |
| 16 | Rosa (1965; cited in Knuth 2025, p. 24) |
| 27 | Aldred and McKay (1998) |
| 28 | Horton (2003) |
| 35 | Fang (2010) |
Fang (2012) later reported an unpublished verification through 39 vertices, but no additional details or published results appear to be available.
Separately, Knuth and Elkies (2021) independently verified and extended through 
the counts of 
-vertex labeled graphs that
are gracefully labeled trees.
An inductive approach to the conjecture is to delete a leaf and designate the graph vertex formerly adjacent to it as the root vertex of the remaining tree. It would therefore suffice to prove that every rooted tree having a graceful labeling admits an extension by one leaf at its root vertex that is also graceful. The singleton graph is graceful. Consequently, this extension property would prove the conjecture by mathematical induction.
Following a suggestion of E. Pegg, Jr. (pers. comm., Aug. 12, 2026), one way to realize such an extension is to insert a gap at 
in the graceful labeling
by increasing every label greater than or equal to 
by 1, then attaching a new leaf
labeled 
to the root vertex. Computation using exhaustive enumeration
through 15 vertices, followed by certificate closure
and targeted exact searches, found that every rooted tree
type through order 22 has a gap and a graceful labeling
for which adding the new leaf gives a graceful tree with one more graph vertex.
In particular, this holds for all 97,055,181 types of rooted
trees on 22 vertices (E. Weisstein, Aug. 20,
2026). Thus the one-step extension property is verified at every order through 22.
This is not yet an inductive proof, since a proof would
have to cover all sizes and might have to choose a new graceful
labeling after each step. Indeed, the stronger requirement that the labeling
produced by one extension itself support a prescribed second extension without relabeling
already fails for rooted trees on 6 vertices.
This does not contradict the one-step verification through 22 vertices.
, 
for 
." 2021.