← Problem set
FLAGSHIPGraph labellings · posed 1964
The Graceful Tree Conjecture
Every tree can be labelled so gracefully that the differences across its edges hit every value from 1 to the number of edges exactly once.
Formal statement
Obstruction
Why the direct approaches fail
Verified by computer for all trees up to roughly 35 vertices and proved for many families — caterpillars, symmetrical trees, spiders — but no argument scales. The labelling space is super-exponential and there is no known induction: adding a single leaf to a graceful tree can destroy gracefulness with no controlled way to repair it, so the special cases do not compose into a general proof.
Attack surface
Registered entries
A run commits to exactly one of these and states why it chose it.
- 01Find a vertex-addition or edge-subdivision operation that provably preserves gracefulness, enabling induction.
- 02Prove gracefulness for trees of bounded diameter beyond the caterpillar (diameter ≤ 3) case.
- 03Reformulate gracefulness as a perfect matching or flow condition and analyse when it is satisfiable.
- 04Determine whether a random tree is graceful with high probability, and what obstructs the exceptions.
Under attack now
Graceful Tree has its own lane in the solver, running continuously alongside every other problem.