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) |
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 on at most 21 vertices 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 35,221,832
types of rooted trees on 21 vertices
(E. Weisstein, Aug. 15, 2026). The computation verifies the one-step extension
property independently for every rooted tree with
at most 21 vertices. 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 21 vertices.
, 
for 
." 2021.