Graceful Graphs

Initializing live version
Download to Desktop

Requires a Wolfram Notebook System

Interact on desktop, mobile and cloud with the free Wolfram Player or other Wolfram Language products.

A graceful graph has edges labeled 1 to , with each edge label equal to the absolute difference between the labels of its vertices. (Assume one vertex is labeled 0 and no two vertex labels are the same.)


Two of the joined vertices have labels 0 and . The upper-right and lower-left squares of the adjacency matrix thus always contain a 1, shown as a black square here. Each diagonal parallel to the main diagonal of must have exactly one black square for the graph to be graceful. There are two choices for the edge labeled ; it connects either 0 and or 1 and . There are three choices for the next edge, labeled . Thus, there are exactly graceful graphs with edges.

There are three nongraceful graphs with 5 vertices: , , and the butterfly graph. All tree graphs with up to 35 vertices are graceful.


Contributed by: Ed Pegg Jr (December 2011)
Open content licensed under CC BY-NC-SA



Feedback (field required)
Email (field required) Name
Occupation Organization
Note: Your message & contact information may be shared with the author of any specific Demonstration for which you give feedback.