An ungraceful graph is a simple graph that does not possess a graceful labeling, i.e., a graph
that is not a graceful graph (Gardner 1972). Such
graphs have also been termed "disgraceful graphs"
(Seoud and Wilson 1993).
The numbers of nonisomorphic ungraceful graphs on ,
2, ... vertices are 0, 1, 2, 4, 12, 30, 85, ... (OEIS
A308556), with the corresponding numbers of
connected ungraceful graphs 0, 0, 0, 0, 3, 6,
34, ... (OEIS A308557), the first few of which
are illustrated above. As can be seen, there are no connected
ungraceful graphs on fewer than five vertices and
exactly three connected ungraceful graphs on five
vertices, namely the butterfly
graph (Horton 2003), cycle graph, and complete graph.
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.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.Seoud,
M. A. and Wilson, R. J. "Some Disgraceful Graphs." Int. J.
Math. Educ. Sci. Tech.24, 435-441, 1993. https://doi.org/10.1080/0020739930240314.Sloane,
N. J. A. Sequences A308556 and A308557 in "The On-Line Encyclopedia of Integer
Sequences."
,
2, ... vertices are 0, 1, 2, 4, 12, 30, 85, ... (OEIS
A308556), with the corresponding numbers of
connected ungraceful graphs 0, 0, 0, 0, 3, 6,
34, ... (OEIS A308557), the first few of which
are illustrated above. As can be seen, there are no connected
ungraceful graphs on fewer than five vertices and
exactly three connected ungraceful graphs on five
vertices, namely the butterfly
graph (Horton 2003), cycle graph 
, and complete graph 
.
