19-Mar-1995

Unsolved Problem 12:

Is every tree graceful?

A graph is a set of points (called vertices) and a set of lines (called edges) joinging these vertices.
A tree is a graph with the property that there is a unique path from any vertex to any other vertex traveling along the edges.
A graph is said to be graceful if you can number the n vertices with the integers from 1 to n and then label each edge with the difference between the numbers at the vertices, in such a way that each edge receives a different label.

For example, a graceful numbering is shown for the following tree with 9 vertices: 

   (5)         (1)---(4)
   /           /
(7)---(3)---(9)---(2)
   \     \
   (6)   (8)
The edge labels are the numbers from 1 to 8.

Reference:

[Bondy 1976]
J. A. Bondy and U. S. R. Murty, Graph Theory with Applications. North Holland. New York: 1976. Page 248.
Graceful Trees
Each week, for your edification, we publish a well-known unsolved mathematics problem. These postings are intended to inform you of some of the difficult, yet interesting, problems that mathematicians are investigating. We do not suggest that you tackle these problems, since mathematicians have been unsuccessfully working on these problems for many years.

general references
previous problem
problem archive
next problem
electronic publications