A maximally graceful graph is a graceful graph that has the maximum possible number of fundamentally distinct graceful labelings among all graphs with the same number of vertices.
The numbers of fundamentally distinct graceful labelings for maximally graceful graphs with 
, 2, ... vertices are illustrated
above for all simple graphs.
Maximally graceful connected graphs are illustrated above.
The counts for all simple graphs, simple graphs with no isolated vertices, and connected graphs are summarized in the following table. Note that the latter two are equal up to at least 10 vertices (E. Weisstein, Feb. 27, 2026).
| OEIS | counts | type |
| A379395 | 1, 1, 1, 5, 26, 126, 680, 3876, 25501, 154231, ... | simple graphs |
| A339892 | 1, 1, 1, 5, 26, 126, 680, 3778, 22033, 127055, ... | simple graphs with no isolated vertices |
| 1, 1, 1, 5, 26, 126, 680, 3778, 22033, 127055, ... | simple connected graphs |
Knuth (2025) considered maximally graceful graphs only among graphs containing no isolated vertices. Those counts
are the same as among all connected and all simple graphs up to 
, but differ at 
: the 8-vertex maximally
graceful connected graph, which also has no isolated vertices, has 3778 (instead of 3876) fundamentally
distinct graceful labelings. This graph
is illustrated above. It is significant for also being the 8-vertex graph having a maximal number (80) of planar
embeddings.
Maximally graceful trees are also considered.
