A maximally graceful graph is a graceful graph that has the maximum possible number of 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 and 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 (2024) 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.
