A sixty-year-old question that is easy to state, easy to check, and — so far — impossible to settle.

The definitions

A tree is a connected graph with no cycles: any two dots are joined by exactly one path. A tree with n vertices has exactly n − 1 edges — one fewer edge than it has vertices, always.

A graceful labelling of a tree T on n vertices is a bijection

f : V(T) → {0, 1, …, n−1}

such that the induced edge labels g(uv) = |f(u) − f(v)| are pairwise distinct.

That last condition is stronger than it looks. There are n − 1 edges, and every edge label necessarily lands in {1, …, n−1}. So if the n − 1 edge labels are all different, they are forced to be exactly the set {1, …, n−1}, each appearing once. Vertices use every number once; edges then use every difference once. Nothing is left over and nothing repeats.

A worked example

Here is a real tree on 8 vertices with a real graceful labelling — the one drawn on the front page. Circled numbers are vertex labels; numbers on the edges are the differences.

Reading the seven edges off the drawing:

Vertex labels: 0, 1, 2, 3, 4, 5, 6, 7 — each used once. Edge labels: 1, 2, 3, 4, 5, 6, 7 — each used once. That is a graceful labelling, and checking it took you a few seconds. Checking one is trivial; finding one is the hard part, and proving one always exists is the part nobody can do.

Why a computer is needed

Verifying the conjecture for a given size n means producing a labelling for every distinct tree on n vertices — distinct meaning non-isomorphic, so relabelled copies of the same shape count once. The number of such trees is the integer sequence OEIS A000055, and it grows fast:

Counts as published in OEIS A000055. Our own code recomputes them independently from Otter's formula before any of them is used to decide that a milestone is complete — a published number we have not reproduced is not evidence.

Six trillion trees, each needing a search. That is the whole reason this is a distributed project rather than a script.

What is already known

This is not virgin ground, and we will not pretend otherwise.

• Aldred and McKay verified the conjecture through 27 vertices; Horton claimed 29.
• Fang (2010) reports exhaustive verification through 35 vertices. That computation already used volunteer machines, so distributed verification is not a new idea we are introducing — it is the established method for this problem.
• A July 2026 preprint by Pajo reports work at n = 36, but on a non-exhaustive 248-tree corpus. It does not close order 36.
• In a 2012 blog post, Fang reported checking every tree up to 39 vertices. The paper it promised never appeared, and no code, data or labelings were released, so that result cannot be checked by anyone.

So we start at n = 36. Orders 36 to 39 have been claimed but the work was never shown; we are checking them in the open, keeping the evidence anyone needs to check us, and then carrying on upward.

What a completed milestone would and would not mean

Suppose we finish order N. The honest statement is:

The distinction is not modesty, it is arithmetic. There are infinitely many trees. Checking six trillion of them settles six trillion cases and leaves infinitely many untouched. A proof would be a mathematical argument covering all sizes at once; no amount of computing produces one.

Two further limits we state up front:

• Completing order 37 does not establish order 36. The orders are independent claims. "Verified through N" requires every intervening order to be finished too.
• We do not archive every labelling. Storing trillions of witnesses is not feasible. We keep samples, cryptographic commitments to the full witness streams, and every exceptional case. That makes this a reproducible computational verification resting on reviewed software — not an independently checkable archive of every witness.

How the search actually works, and how we check it →