A

David

Darling

graceful graph

A graceful graph with 27 edges and 9 vertices.

A graceful graph with 27 edges and 9 vertices.


A graceful graph is a graph of points and connecting lines that can be numbered in a certain way. Say the graph has p points and e lines ("e" for edges) connecting them. Each of the points is assigned an integer; the lowest integer (by convention) is taken to be 0, and no two integers may be alike. Each of the lines is labeled with the difference between the two integers of the points that it connects. Then, if the numbers corresponding with the lines run from 0 through e, the graph is said to be graceful. Graceful graphs were originally defined and developed by Solomon Golomb.