A tree is a network of dots and lines with no loops. A graceful labelling numbers its n dots 0, 1, …, n−1 so that the n−1 lines, each measuring the gap between the two dots it joins, come out with every gap from 1 to n−1 appearing exactly once.

In 1967 Ringel and Kotzig conjectured that every tree can be labelled this way. It is still open. Nobody has found a tree that resists, and nobody has shown that none exists.

We attack the finite version: take every distinct tree of a given size and find a graceful labelling for each one. The count grows viciously — there are over six trillion distinct trees on 36 dots — which is why this needs your computer and not just ours.

What the conjecture says, and what we can honestly claim →

Already joined? Log in.