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 ungraceful graphs on 
, 2, ... nodes 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 vertives and exactly three connected ungraceful graphs on five vertices,
namely the butterfly graph (Horton 2003), cycle
graph 
,
and complete graph 
.
See also
Graceful Graph,
Graceful
Labeling
Explore with Wolfram|Alpha
References
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. University of Tasmania,
2003. https://eprints.utas.edu.au/19/1/GracefulTreesStatisticsAndAlgorithms.pdf.Seoud,
M. A. and Wilson, R. J. "Some Disgraceful Graphs." Int. J.
Math. Educ. Sci. Tech. 24, 435-441, 1993.Referenced on Wolfram|Alpha
Ungraceful Graph
Cite this as:
Weisstein, Eric W. "Ungraceful Graph."
From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/UngracefulGraph.html
