Graceful Graph

A graceful graph is a graph that can be gracefully labeled. Special cases of graceful graphs include the utility graph (Gardner 1983) and Petersen graph. A graph that cannot be gracefully labeled is called an ungraceful (or sometimes disgraceful) graph.

Graceful graphs may be connected or disconnected; for example, the graph disjoint union of the singleton graph and a complete graph is graceful iff or .

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 2025, p. 5).

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).

In order for a graph to be graceful, it must be without loops or multiple edges. A graph on vertices and edges must also satisfy

in order to be graceful, since otherwise there are not enough integers less than or equal to to cover all the vertices. Another criterion for determining that a graph is ungraceful is due to Rosa (1967), who proved that an Eulerian graph with edge count congruent to 1 or 2 (mod 4) is ungraceful.

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 connected ungraceful graphs 0, 0, 0, 0, 3, 6, 34, ... (OEIS A308557), the first few of which are illustrated above.

Pegg (2019) considered the minimum edge count of a graceful regular graph with vertex degree . For , 1, ..., the known values begin 0, 1, 3, 6, 12, 20, 27, 35, 48, 63, 75, 99, 108, ... (OEIS A308722), and Pegg (2019) verified . Knuth (2025, §7.2.2.3, Exercise 93 and its answer) considers how to enumerate the graceful labelings of regular graphs with prescribed edge count and vertex degree. This problem is related to sparse rulers. The graph vertex labels of a graceful regular graph with edges and vertex degree give distinct integer marks whose pairwise differences have absolute values including every distance from 1 through . A single pair must be selected for each distance so that every graph vertex belongs to exactly selected pairs (Pegg 2019, 2024).

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).

A graph that contains a single fundamentally distinct graceful labeling (i.e., a unique graceful labeling modulo the graph automorphism group and with respect to subtractive complementation) may be termed a uniquely graceful graph, and a graph possessing the maximum possible number of fundamentally distinct graceful labelings (possibly subject to some additional condition such as possessing no isolated vertices) may be termed a maximally graceful graph.

Parametrized families of graceful graphs include the following:

1. antiprism graphs,

2. banana trees,

3. book graphs ,

4. Cameron graphs,

5. caterpillar graphs,

6. complete graphs iff (Golomb 1974),

7. complete bipartite graphs (Golomb 1974),

8. crossed prism graphs,

9. cycle graphs iff ,

10. firecracker graphs,

11. gear graphs,

12. grid graphs ,

13. helm graphs,

14. hypercube graphs ,

15. ladder graphs ,

16. Lindgren-Sousselier graphs,

17. Möbius ladders ,

18. Mongolian tent graphs,

19. pan graphs,

20. path graphs ,

21. Platonic graphs (Gardner 1983, pp. 158 and 163-164),

22. prism graphs ,

23. star graphs ,

24. sunlet graphs ,

25. tadpole graphs,

26. web graphs, and

27. wheel graphs (Frucht 1988).

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 connected unicyclic graphs except the cycle graph with or 2 (mod 4) are graceful (Truszczyński 1984; Gallian 2025, p. 18).