A labelling every tree seems to have

Sixteen trees on four points counted the ways to join labelled points into a tree, and the essays after it studied what a random one looks like. This essay turns the labels around. Instead of asking how many trees a set of labelled points supports, it takes a tree and asks whether its points can be labelled in a particular, demanding way — one that every tree seems to allow and no proof shows every tree must.

Take a tree with $n$ points, so $n - 1$ edges. Write the numbers $0, 1, \ldots, n - 1$ on the points, each used once, and on each edge write the difference between the numbers at its two ends. There are $n - 1$ edges and the differences lie between 1 and $n - 1$, so it is possible, in principle, for the edges to carry every difference exactly once. A labelling that achieves it is called graceful.

The graceful tree conjecture says every tree has one. Gerhard Ringel and Anton Kotzig posed it in the 1960s, Alexander Rosa gave the labellings their first careful study in 1967, and Solomon Golomb named them graceful in 1972. It has been checked by computer for every tree with up to about thirty-five points. It has been proved for paths, stars, caterpillars and many other families. For trees in general it is open, and it has become one of the best-known unsolved problems about graphs — partly because it is so easy to state that anyone can try it on a napkin, and partly because everyone who does finds a labelling.

Four trees on seven points #

The four trees in the figure show the range. A path on seven points has the labelling $0, 6, 1, 5, 2, 4, 3$ read along it: the differences are $6, 5, 4, 3, 2, 1$, each once. That zigzag works for a path of any length, and it is the first proof anybody gives. A star, one centre with six leaves, is easier still: label the centre 0 and the leaves 1 to 6, and each edge’s difference is its leaf’s label.

A caterpillar — a path with leaves hanging off it — and a spider — several paths joined at one point — need a little more thought, and the search found labellings for both in a few dozen steps. Rosa proved in 1967 that every caterpillar is graceful, by a construction that extends the path’s zigzag to the hanging leaves. Spiders are known graceful in many cases and not in general. The figure’s labellings were found by a search that tries labels point by point and backs up whenever an edge difference repeats.

The difficulty of the general case is visible even here. Each family is labelled by its own construction, adapted to its shape. A general proof would need a construction that works for every shape at once, or an argument that a labelling exists without constructing it — and neither has been found.

Every tree on eight points #

There are 23 different trees on eight points, counting two trees as the same if one can be redrawn as the other. The figure draws every one of them with a graceful labelling. The trees were generated by adding a leaf in every possible place to every tree on seven points and discarding duplicates, and the count was checked against the known sequence $1, 1, 1, 2, 3, 6, 11, 23, 47, 106, 235, 551$ for one to twelve points. Those are unlabelled trees, shapes without names on their points; the labelled count $n^{n-2}$ of sixteen trees on four points counts each shape once for every way of naming its points, and the bijections of cars that park, and trees that grow work with the labelled kind.

The labellings are not unique, and they look arbitrary. Nothing in the figure suggests a rule: the same shape of subtree is labelled differently in different trees, and the labels at the centres range over the whole of $0$ to $7$. The labelling is a global object — every edge’s difference must differ from every other’s — and a local rule would have to anticipate what happens everywhere else in the tree.

This is also why the search is the natural tool. Assign labels to the points one at a time, in order outward from a starting point, and reject any label that repeats a point label or produces an edge difference already used. For trees on eight points it never needed more than 1,621 steps.

Every tree up to twelve points #

The same search, run on every tree from two points to twelve, finds a graceful labelling every time — 986 trees in all. The number of trees grows by a factor of about three with each added point, and the steps the plain search needs grow faster: the average rises from a handful at five points to tens of thousands at eleven, and the worst tree at eleven points needed over seven hundred thousand.

That growth is why the checks to about thirty-five points needed much cleverer searches — ordering the choices, labelling edges rather than points, exploiting the fact that the largest difference $n - 1$ forces the labels $0$ and $n - 1$ to be neighbours. The number of trees makes the ceiling unavoidable. At thirty-five points there are about $2 \times 10^{12}$ trees, each needing its own labelling; and the number of trees passes the number of atoms in the Earth somewhere near a hundred and twenty points. No computation will ever check the conjecture for all trees of that size, and a proof is the only way it can be settled.

Some trees have few labellings, none has none #

Counting every graceful labelling of every tree, rather than stopping at the first, shows how much room there is. For trees on nine points the counts run from 120 to 80,640. The star has the most: its centre must be 0 or 8 — any other centre label would repeat a difference — and then the leaves can be labelled in any order, $2 \times 8!$ ways. The trees with the fewest are long and thin, and the path is often among them, with 120 labellings at nine points.

The minimum is the telling number. If some tree had no graceful labelling, the lower line in the figure would have to reach nought at some size. In the range computed it grows steadily, from 4 at three points to 120 at nine, and the least graceful tree has more labellings, not fewer, as the trees get larger. That is evidence of the kind that makes people believe the conjecture — and exactly the kind that small cases have made misleading before, since a trend over nine points is a trend over forty-seven trees.

Every labelling also comes with a partner: replacing each label $l$ by $n - 1 - l$ keeps every difference the same, so the counts are always even, and the complement of a graceful labelling is graceful. The fewest possible for a tree that has any labelling at all is therefore two.

Why Ringel wanted it: tiling the complete graph #

The conjecture was not asked for its own sake. Gerhard Ringel conjectured in 1963 that for any tree $T$ with $n$ edges, the complete graph on $2n + 1$ points — every pair of points joined — can be split into $2n + 1$ copies of $T$, each edge of the complete graph used in exactly one copy. The complete graph on $2n + 1$ points has $n(2n + 1)$ edges, exactly $2n + 1$ times $n$, so the count is right; the question is whether the pieces fit.

A graceful labelling makes them fit. Place the $2n + 1$ points round a circle and number them $0$ to $2n$. The edges of the complete graph come in $n$ lengths, measured the short way round the circle, and exactly $2n + 1$ edges of each length. A tree gracefully labelled with $0$ to $n$ has one edge of each length $1, \ldots, n$. Put it on the circle at its labels, then turn it one position at a time: each turn moves every edge to another of the same length, and the $2n + 1$ turns reach each edge of each length exactly once. The figure does it for a path with three edges on seven points.

Rosa observed this in 1967, and it is the reason graceful labellings were studied at all: the graceful tree conjecture implies Ringel’s. Ringel’s conjecture was proved in 2020, for all sufficiently large $n$, by Richard Montgomery, Alexey Pokrovskiy and Benny Sudakov, and independently by Peter Keevash and Katherine Staden. Their proofs use probabilistic methods and absorbers — structures that soak up whatever the random part of the construction leaves over — and produce the tiling without producing a graceful labelling. The stronger conjecture that motivated the weaker one is still open after the weaker one has been settled.

A random tree, labelled the hard way #

The tree in the last figure was drawn at random from all $16^{14}$ labelled trees on sixteen points, by the Prüfer correspondence of sixteen trees on four points, and its shape is typical of a random tree — bushy near a few points, with about one point in $e$ a leaf, as a random tree is one part in e leaves found. The plain search labelled it in about 1.6 million steps. On other random trees of the same size the same search needed tens or hundreds of millions.

A cleverer search works on the differences rather than the points. The largest difference, $n - 1$, can only arise between the labels $0$ and $n - 1$, so those two labels must sit at the ends of some edge. The next, $n - 2$, arises only from the pairs $(0, n-2)$ and $(1, n-1)$, so one of those must be an edge — and either way it shares a point with the first, since each pair contains $0$ or $n - 1$. The two largest differences therefore sit on two edges that meet, a path of two steps somewhere in the tree. Working down the differences in this way, each step has at most two choices of where the next difference can come from, and the choices interact with the tree’s shape early, when a wrong turn is cheap to undo. Searches built on observations of this kind, rather than on trying labels point by point, are what carried the verification to around thirty-five points.

That spread is itself informative. If labellings were rare, some trees would take astronomically long to label and others would have none; if they were abundant, every tree would be labelled quickly by any reasonable search. The truth is in between and depends on the order in which choices are made, which is why the large verifications depend on careful ordering. The existence of a labelling has never been in doubt for any tree anyone has tried; the time to find one has.

The same trick, in designs and rulers #

The rotation that turns a graceful tree into a tiling is an old idea in combinatorial design, and its purest form needs no tree at all. A plane in a list of numbers built the projective plane of order 2 from the numbers $\{0, 1, 3\}$ modulo 7: their six differences, $\pm 1, \pm 2, \pm 3$, cover every non-zero remainder exactly once, so turning the set round the circle of seven positions produces seven triples in which every pair of points appears exactly once. That is a perfect difference set, and a graceful labelling of a tree is the same idea applied to the tree’s edges instead of all pairs of a set.

The same property of differences defines a Golomb ruler, named after the same Solomon Golomb who named graceful labellings: a set of marks at whole-number positions with all pairwise distances different. A ruler whose distances are exactly $1, 2, \ldots, m$ is a perfect ruler, and perfect rulers exist only with up to four marks — $\{0, 1, 4, 6\}$ is the largest. A graceful labelling asks for a perfect set of differences along the edges of a tree rather than across all pairs, which is a much weaker demand, and that is why it can be met far more often.

A schedule where every pair meets once is the design version of Ringel’s question with the tree replaced by a triangle: split the complete graph on $n$ points into triangles, each edge used once. Kirkman settled when that is possible in 1847. For triangles the answer is a congruence condition on $n$; for trees, whose shapes vary without limit, Ringel’s conjecture needed the full weight of modern probabilistic combinatorics, and the graceful version needs something no one has yet found.

What is known for special trees #

The families known to be graceful are many and scattered. Caterpillars, by Rosa’s construction. Trees with at most four leaves. Trees of diameter at most five — every point within five steps of every other — by a case analysis completed in 2001. Olive trees, many spiders and many lobsters, each by a construction tailored to its shape. Each result extends the frontier a little, and none has suggested a method that reaches all trees.

A different line of attack weakens the requirement. Allow the labels to be larger than $n - 1$, or ask only that the differences be distinct rather than exactly $1$ to $n - 1$, and much more can be proved. Anna Adamaszek, Peter Allen, Codruţ Grosu and Jan Hladký showed that almost every tree is almost graceful: with labels allowed to run a little beyond $n - 1$, almost every large tree has a labelling with all its differences distinct. Each relaxation is a statement about how nearly graceful every tree is, and none closes the last gap. Two trees and every edge met a related theme, in which a graph is split into trees rather than a complete graph into copies of one tree; decomposition questions of this kind are easy to state and notoriously hard to settle in general.

Still open: every tree #

The graceful tree conjecture remains open: it is not known that every tree has a graceful labelling. It is not even known that every lobster — a tree that becomes a caterpillar when its leaves are removed — has one, a special case posed by Jean-Claude Bermond in 1979 that has attracted decades of attention on its own.

What makes it hard is that the condition is exact and global. A labelling that is nearly graceful — all differences distinct but one repeated — is useless, and a partial labelling that is graceful so far can be impossible to complete for reasons that only appear at the last edge. Probabilistic methods, which proved Ringel’s conjecture, work by allowing a small amount of waste and repairing it, and a graceful labelling allows no waste at all.

What the figures cannot show #

Every labelling in the figures was found by exhaustive backtracking and checked edge by edge — every point label used once, every difference used once — so each drawn labelling is certainly graceful whatever the search that produced it; every tree up to twelve points was generated and labelled; every labelling of every tree up to nine points was counted. Those are complete statements about the trees they cover. The conjecture is about all trees, and at the sizes the figures reach, the smallest counterexample, if one exists, is already known to lie beyond about thirty-five points.

The trends — counts that grow, searches that succeed — are the reason most people believe the conjecture, and they are exactly the kind of evidence that small cases can make misleading. Trees on thirty-five points are still small, and the conjecture is a claim about trees on a million.