An Unsolved Problem in Graph Theory

The Graceful Tree Conjecture

This post is a collection of notes about an interesting unproven problem in combinatorics. The Kotzig-Ringel conjecture, better known as the Graceful Tree Conjecture (GTC), claims that:

All trees are graceful.

This is a simple statement but mathematicians don’t know if it’s true or not! At the time of this writing, nobody has come up with a counterexample and there is no proof that one exists.

Before discussing trees, let’s consider the broader category of simple graphs. Simple graphs are finite undirected graphs with no self-adjacent vertices or duplicated edges. The labeling of a simple graph assigns an integer to each of its vertices and edges. (The British spelling is labelling .)

In a graceful labeling, each edge label (E ij ) is the absolute difference between the labels of its adjoining vertices (V i and V j ).

If a graceful graph has n edges, then labels V i and E ij can be assigned to its vertices and edges such that:

V i ∈ {0, 1, … , n}
V i ≠ V j for all i,j
E ij ∈ {1, … , n}
E ij = | V i - V j |

Figure 1 depicts an example of a graph with graceful labels.

Figure 1. Graceful graph with three edges.

A complementary graceful labeling can be generated by subtracting each vertex label from n , as shown in the next figure. This shows that a given graph might permit more than one graceful labeling.

Figure 2. The graceful complement of Figure 1.

Graphs that are trees are simple, connected, and acyclic. This implies that trees exhibit the property V=E+1 where V is the number of vertices and E is the number of edges. Therefore, if you only consider graceful graphs that happen to be trees, you must use each vertex label in {0, 1, … , n} exactly once, and you must use each edge label in {1, … , n} exactly once.

(Once way of remembering V=E+1 is to apply Euler’s Polyhedron Formula with only one face. Since trees have no cycles, they do not divide the plane.)

Figure 3 depicts a graceful tree. The edge labels are easy to compute so they are left as an exercise to the reader. While this happens to be a rooted tree, please note that the conjecture applies to all trees, even if they are unrooted.

Figure 3. Graceful graph with five edges.

Representing graceful graphs

One neat thing about a graceful labeling is that you don’t need to draw out the graph in order to uniquely identify it. Every graceful labeling can be represented with a sequence of positive integers that has the following property.

For a positive integer m, the sequence of integers ( j 1 , j 2 , j 3 , … , j m ) is a labeling sequence if 0≤j i ≤m-i for all i ∈ [1,m].

To construct a graph from an integer sequence with m terms, follow this two-step process:

Assign the integers in [0,m] to isolated vertices.
For each term j i in the sequence, draw an edge between j i and j i + i.

The integer sequences for the graphs in Figures 1 through 3 are shown below.

(0, 1, 0)
(2, 0, 0)
(3, 2, 1, 0, 0)

Next we demonstrate how to apply the two-step process:

(0, 1, 0) + (1, 2, 3) = (1, 3, 3)
(2, 0, 0) + (1, 2, 3) = (3, 2, 3)
(3, 2, 1, 0, 0) + (1, 2, 3, 4, 5) = (4, 4, 4, 4, 5)

The three graphs can be rendered from the above list by connecting each term in the left boldface sequence with its corresponding term in the right boldface sequence.

Conversely, to construct a sequence from a labeled graph, do this:

Go through the edges in order from 1 to n .
For each edge, pick the smaller of its two endpoint labels, and append it to the sequence.

These sequences were first demonstrated by David Sheppard in 1974. If you can prove that every acyclic connected graph (i.e. every tree) has a corresponding Sheppard sequence, then you can prove the conjecture and make history.

Counting graceful graphs

The mapping between those special integer sequences and graceful graphs implies that there exist n! graceful graphs that have n edges. Another way of coming to this conclusion is to consider each of the edge values, one by one, starting with the greatest edge value.

For example, if edge labels are in [1,5] and vertex labels are in [0,5], then:

The edge with label 5 must be between the vertex with label 0 and the vertex with label 5.

The above statement is always true in a graceful graph with 5 edges, because those two vertices are only ones that are sufficiently far apart. Similarly:

The edge with label 4 must either (a) lie between vertex 0 and vertex 4, or (b) lie between
vertex 1 and vertex 5.

So, there is 1 possibility for placing the “5” edge, and 2 possibilities for placing the “4” edge. If you continue this line of thought, a pattern emerges as the number of possible edge placements increases: 1 possibility, times 2 possibilities, times 3 possibilities…

The n! conclusion is all well and good for general graphs, but the more constrained problem of trees seems to have eluded mathematicians. I don’t think anybody has come up with a closed form solution for “number of graceful trees with n edges”.

Just for fun, here are some SVG diagrams of graceful trees along with their corresponding Sheppard sequences. The complement of each labelling is shown on the right. This list is limited to trees with 3 edges, 4 edges, and 5 edges.

(0, 0, 0) and (2, 1, 0)