Although an unpublished result of Erdős says that most graphs are not graceful (Graham and Sloane 1980), most graphs
that have some sort of regularity of structure are graceful (Gallian 2026).
It is an unsolved and apparently very difficult problem to determine which graphs are graceful. One reason for its difficulty is that a subgraph
of a graceful graph need not be graceful (Seoud and Wilson 1993).
The numbers of nonisomorphic graceful graphs on , 2, ... nodes are
1, 1, 2, 7, 22, 126, ... (OEIS A308548), while
the corresponding numbers of connected graceful
graphs are 1, 1, 2, 6, 18, 106, ... (OEIS A308549).
The numbers of ungraceful graphs on , 2, ... nodes are
0, 1, 2, 4, 12, 30, 85, ... (OEIS A308556),
with the corresponding numbers of connectedungraceful graphs 0, 0, 0, 0, 3, 6, 34, ... (OEIS
A308557), the first few of which are illustrated
above.
Pegg (2019, 2024) conjectured that for . However, S. Li proved
that no graceful regular graph with vertex
degree 16 and edge count 192 exists, thereby refuting
this conjecture (D. E. Knuth, pers. comm.
to S. Li, Oct. 5, 2026). As of that communication, existence remained open
for graceful regular graphs with vertex
degree 16 and edge count 200, or vertex
degree 18 and edge count 243. These graphs
would have vertex count 25 and 27, respectively (D. E. Knuth,
pers. comm. to S. Li, Oct. 5, 2026).
The -barbell graph is ungraceful
from
up to at least
(E. Weisstein, Sep. 19, 2025) and likely for all larger .
In 1965, Kotzig conjectured that all trees are graceful, an almost certainly true conjecture known as the graceful tree conjecture that remains unproven
to this day.
It has also been conjectured that all connectedunicyclic graphs except the cycle
graph
with
or 2 (mod 4) are graceful (Truszczyński 1984, Gallian 2026).
Abraham, J. and Kotzig, A. "Extensions of Graceful Valuations of 2-Regular Graphs Consisting of 4-Gons." Ars Combin.32,
257-262, 1991.Abraham, J. and Kotzig, A. "All 2-Regular Graphs
Consisting of 4-Cycles are Graceful." Disc. Math.135, 1-24, 1994.Aldred,
R. E. L. and McKay, B. "Graceful and Harmonious Labellings of Trees."
Bull. Inst. Combin. Appl.23, 69-72, 1998.Bloom, G. S.
and Golomb, S. W. "Applications of Numbered Unidirected Graphs." Proc.
IEEE65, 562-570, 1977.Bolian, L. and Xiankun, Z. "On
Harmonious Labellings of Graphs." Ars Combin.36, 315-326, 1993.Bondy,
J. A. and Murty, U. S. R. Graph
Theory with Applications. New York: North Holland, p. 248, 1976.Brualdi,
R. A. and McDougal, K. F. "Semibandwidth of Bipartite Graphs and Matrices."
Ars Combin.30, 275-287, 1990.Brundage,
M. "Graceful Graphs." http://www.qbrundage.com/michaelb/pubs/graceful/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 Th.4,
409-415, 1980.Eshghi, K. and Azimi, P. "Applications of Mathematical
Programming in Graceful Labeling of Graphs." J. Appl. Math.2004,
no. 1, 1-8, 2004.Frucht, R. W. and Gallian, J. A. "Labelling
Prisms." Ars Combin.26, 69-82, 1988.Gallian, J. A.
§§1 and 2.2 in "A Dynamic Survey of Graph Labeling." Elec.
J. Combin., Dynamic Survey DS6, Nov. 6, 2026. https://doi.org/10.37236/27.Gallian,
J. A. "A Survey: Recent Results, Conjectures, and Open Problems in Labelling
Graphs." J. Graph Th.13, 491-504, 1989.Gallian,
J. A. "Open Problems in Grid Labeling." Amer. Math. Monthly97,
133-135, 1990.Gallian, J. A. "A Guide to the Graph Labelling
Zoo." Disc. Appl. Math.49, 213-229, 1994.Gallian,
J. A.; Prout, J.; and Winters, S. "Graceful and Harmonious Labellings of
Prism Related Graphs." Ars Combin.34, 213-222, 1992.Gardner,
M. "Mathematical Games: The Graceful Graphs of Solomon Golomb, or How to Number
a Graph Parsimoniously." Sci. Amer.226, No. 3, 108-113,
March 1972.Gardner, M. "Golomb's Graceful Graphs." Ch. 15
in Wheels,
Life, and Other Mathematical Amusements. New York: W. H. Freeman,
pp. 152-165, 1983.Golomb, S. W. "How to Number a Graph."
In Graph
Theory and Computing (Ed. R. C. Read). New York: Academic Press,
pp. 23-37, 1972.Golomb, S. W. "The Largest Graceful Subgraph
of the Complete Graph." Amer. Math. Monthly81, 499-501, 1974.Graham,
R. L. and Sloane, N. J. A. "On Additive Bases and Harmonious
Graphs." SIAM J. Alg. Discrete Methods1, 382-404, 1980.Guy,
R. "Monthly Research Problems, 1969-75." Amer. Math. Monthly82,
995-1004, 1975.Guy, R. "Monthly Research Problems, 1969-1979."
Amer. Math. Monthly86, 847-852, 1979.Guy, R. K.
"The Corresponding Modular Covering Problem. Harmonious Labelling of Graphs."
§C13 in Unsolved
Problems in Number Theory, 2nd ed. New York: Springer-Verlag, pp. 127-128,
1994.Horton, M. "Graceful Trees: Statistics and Algorithms."
Bachelor of Computing with Honours thesis. Hobart, Tasmania, Australia: University
of Tasmania, 2003. https://doi.org/10.25959/23212346.Huang,
J. H. and Skiena, S. "Gracefully Labelling Prisms." Ars Combin.38,
225-242, 1994.Jungreis, D. S. and Reid, M. "Labelling Grids."
Ars Combin.34, 167-182, 1992.Knuth, D. E. §7.2.2.3,
including Exercise 93 and its answer, in The
Art of Computer Programming, Vol. 4, Fascicle 7: Constraint Satisfaction.
Boston, MA: Addison-Wesley, pp. 16-24, 121 and 178, 2025.Koh, K. M.
and Punnim, N. "On Graceful Graphs: Cycles with 3-Consecutive Chords."
Bull. Malaysian Math. Soc.5, 49-64, 1982.Koh, K. M.
and Yap, K. Y. "Graceful Numberings of Cycles with a -Chord." Bull. Inst. Math. Acad. Sinica13,
41-48, 1985.Moulton, D. "Graceful Labellings of Triangular Snakes."
Ars Combin.28, 3-13, 1989.Nikoloski, Z.; Deo, N.; and
Suraweera, F. "Generation of Graceful Trees." Congr. Numer.157,
191-201, 2002.Pegg, E. Jr. "Graceful Graphs with Valence ." May 31, 2019. https://math.stackexchange.com/questions/3246000/graceful-graphs-with-valence-k.Pegg,
E. Jr. "Does a 16-Valence 192-Edge Graceful Graph Exist?" Dec. 11,
2024. https://math.stackexchange.com/questions/5010303/does-a-16-valence-192-edge-graceful-graph-exist.Punnim,
N. and Pabhapote, N. "On Graceful Graphs: Cycles with a -Chord, ." Ars Combin. A23, 225-228, 1987.Rosa,
A. "On Certain Valuations of the Vertices of a Graph." In Theory of
Graphs, International Symposium, Rome, July 1966. New York: Gordon and Breach,
pp. 349-355, 1967.Seoud, M. A. and Wilson, R. J. "Some
Disgraceful Graphs." Int. J. Math. Educ. Sci. Tech.24, 435-441,
1993.Sierksma, G. and Hoogeveen, H. "Seven Criteria for Integer
Sequences Being Graphic." J. Graph Th.15, 223-231, 1991.Slater,
P. J. "Note on -Graceful, Locally Finite Graphs." J. Combin. Th. Ser.
B35, 319-322, 1983.Sloane, N. J. A. Sequences
A308544, A308545,
A308548, A308549,
A308556, A308557,
and A308722 in "The On-Line Encyclopedia
of Integer Sequences."Snevily, H. S. "New Families of
Graphs That Have -Labellings."
Preprint.Snevily, H. S. "Remarks on the Graceful Tree Conjecture."
Preprint.Truszczyński, M. "Graceful Unicyclic Graphs."
Demonstatio Math.17, 377-387, 1984.Xie, L. T. and
Liu, G. Z. "A Survey of the Problem of Graceful Trees." Qufu Shiyuan
Xuebao1, 8-15, 1984.