# Graceful Graphs

## Introduction

Occasionally mathematics provides problems which simultaneously challenge professional mathematicians and yet put original results within reach of motivated high school or undergraduate students. Gracefully labelling graphs is one such problem. To date, most research has focused on specific classes of graphs, and few general results are known.

Consider an undirected graph with N edges. Label each vertex of the graph with one of the numbers from 0 to N inclusive. Not every number must be used, but no number may be used more than once. Now label each edge with the absolute difference of the labels of its endpoints. The labeling is graceful if the edges are labelled 1 through N inclusive (no number repeated). A graceful graph is a graph that has at least one graceful labeling.

Figure 1-1 below depicts a graceful labeling of the complete graph on four vertices, K4. The graph has six edges, so the integers 0 through 6, inclusive, are available for vertex labels. If we use the numbers 0, 1, 4, and 6, and compute the edge labels, then every number from 1 to 6 appears as an edge label. Therefore, K4 is graceful.

Figure 1-1: A graceful graph with six edges.

Graceful graphs are attractive to mathematicians because they are so easy to describe, yet lead to many difficult (and as yet unanswered) questions and computational problems. Perhaps the most outstanding one is: Are all trees graceful? But there are many other questions surrounding graceful graphs.

Graceful graphs are related to many other mathematical topics including Golomb rulers, permutations, and other graph labeling problems. They have some practical applications such as radio astronomy, but for the most part graceful graphs are just mathematical curiosities.

## Explore Graceful Graphs

• Bibliography
• Enumerated lists of graceful graphs
• Source code