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 simples graphs, simple graphs with no isolated points, and connected graphs are summarized in the following table. Not 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 points |
| 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 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.
