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.