The Graceful Labeling Problem

So what's this picture? What you see is a graph that has been gracefully labeled. Formally, the definition of the graceful labeling problem is as follows. Let G be a graph of order n and size m. A one-to-one function f: V(G) → {0, 1, 2, ... , m} is called a graceful labeling of G if the induced edge labeling f': E(G) → {1, 2, ... , m}, defined by f'(e) = |f(u) - f(v)| for each edge e=uv in G is also one-to-one. If such a labeling can be constructed, then we call G a graceful graph.

That's a lot of jargon! A less formal, as well as more intuitive, way to define the graceful labeling problem is by construction. Uniquely label the vertices of a graph G with numbers from the set {0, 1, 2, ... , m}. Then label each edge with the absolute difference of the labels on the vertices that edge connects. If, after doing this, each edge is uniquely labeled, then the labeling is graceful.

Feel free to try out some examples yourself! Small graphs are not especially difficult to gracefully label, and it is a fun mathematical game to do. Now, not just any graph is graceful, and the question of which graphs can be labeled in this way and which ones cannot is an unsolved problem that is over 50 years old! Here is a giant survey of results mathematicians have come up with over the years for the gracefulness of a mind-blowing variety of graphs.