In 1965, Kotzig conjectured that all trees are graceful (Bondy and Murty 1976; Knuth 2024, p. 24). While many authors have tried to
prove this and despite the fact that "the GTC is almost certainly true"
(Knuth 2024, p. 24), no proof or refutation has been discovered to date.
Since a tree on vertiecs has edges, all values 0 to appear in any graceful
labeling of its vertices. As a result, the edge label can occur only when the edge in question is incident on
vertices with labels 0 and , meaning vertex labels 0 and must occur at adjacent vertices in a graceful labeling (Hotron
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 theorem has been checked are summarized in
the following table.
reference
16
Rosa (1965; cited in Knuth 2024, p. 24)
27
Aldred and McKay (1998)
28
Horton (2003)
35
Anick (2016) enumerated trees on up to 16 vertices (16 edges) having a maximum number of fundamentally distinct graceful labelings.
(Note that the counts so presented include both subtractively complementary labelings
are so are a factor of 2 times the usual "fundamentally distinct" labeling
counts.)
Aldred, R. E. L. and McKay, B. "Graceful and Harmonious Labellings of Trees." Bull. Inst. Combin. Appl.23,
69-72, 1998.Anick, D. "Counting Graceful Labelings of Trees: A
Theoretical and Empirical Study." Disc. Appl. Math.198, 65-81,
2016.Bondy, J. A. and Murty, U. S. R. Graph
Theory with Applications. New York: North Holland, p. 248, 1976.Cahit,
I. "Are All Complete Binary Trees Graceful?" Amer. Math. Monthly83,
35-37, 1976.Delorme, C.; Maheo, M.; Thuillier, H.; Koh, K. M.;
and Teo, H. K. "Cycles with a Chord are Graceful." J. Graph Theory4,
409-415, 1980.Gallian, J. A. "A Survey: Recent Results, Conjectures,
and Open Problems in Labelling Graphs." J. Graph Th.13, 491-504,
1989.Gallian, J. "Dynamic Survey of Graph Labeling." Elec.
J. Combin.DS6. Dec. 21, 2018. https://www.combinatorics.org/ojs/index.php/eljc/article/view/DS6.Horton,
M. "Graceful Trees: Statistics and Algorithms." Bachelor of Computing with
Honours thesis. University of Tasmania, 2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.Knuth,
D. E. §7.2.2.3 in The
Art of Computer Programming, Vol. 4B: Combinatorial Algorithms, Part 2.
New York: Addison-Wesley, 2022.Nikoloski, Z.; Deo, N.; and Suraweera,
F. "Generation of Graceful Trees." In 33rd Southeastern International
Conference on Combinatorics, Graph Theory and Computing. 2002.Seoud,
M. A. and Wilson, R. J. "Some Disgraceful Graphs." Int. J.
Math. Educ. Sci. Tech.24, 435-441, 1993.Snevily, H. S.
"Remarks on the Graceful Tree Conjecture." Preprint.Xie, L. T.
and Liu, G. Z. "A Survey of the Problem of Graceful Trees." Qufu
Shiyuan Xuebao1, 8-15, 1984.
vertiecs has 
edges, all values 0 to 
appear in any graceful
labeling of its vertices. As a result, the edge label 
can occur only when the edge in question is incident on
vertices with labels 0 and 
, meaning vertex labels 0 and 
must occur at adjacent vertices in a graceful labeling (Hotron
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).
up to which the theorem has been checked are summarized in
the following table.
