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 of various types on 
, 2, ... vertices are summarized in the following table and
illustrated above for all simple graphs.
| OEIS | counts | type |
| A379395 | 1, 1, 1, 5, 26, 126, 680, 3876, ... | simple graphs |
| A339892 | 1, 1, 1, 5, 26, 126, 680, 3778, ... | simple graphs with no isolated points |
| 1, 1, 1, 5, 26, 126, 680, 3778, ... | simple connected graphs |
Knuth (2024) considered maximally graceful graphs only among graphs containing no isolated points. Those counts are the same as among
all connected and all simple graphs up to 
, but differ at 
, with the 8-vertex maximally graceful connected (and no-isolated-point)
graph having 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.
