Graceful Tree Conjecture
Canonical statement
View source LaTeX
Every tree \(T\) with \(m\) edges admits a bijection
\(\ell:V(T)\to\{0,1,\ldots,m\}\) such that
\[
\{\,|\ell(u)-\ell(v)|:uv\in E(T)\,\}
=\{1,2,\ldots,m\}.
\]Notes
The graceful tree conjecture asks that every tree with edges admit a graceful labeling: a bijection under which the absolute differences across the edges realize each of exactly once. The problem dates to the 1960s; graceful labelings (originally -valuations) were introduced by Rosa [Rosa1967Graceful], motivated by decomposition problems for complete graphs, and the now-standard formulation of the conjecture stems from that period.
Many families of trees are known to be graceful — paths, stars, and caterpillars are classical examples — and the conjecture has been confirmed by exhaustive computation for all trees over large finite ranges of sizes. The extensive literature of constructions for special tree families is tracked in Gallian's dynamic survey of graph labelings [Gallian2025Labeling].
No labeling scheme is known that works for arbitrary trees, however; a resolution requires either a genuinely general construction or a tree admitting no graceful labeling, and the conjecture remains open.
References (2)
- [Rosa1967Graceful]
On certain valuations of the vertices of a graph
Alexander Rosa · 1967 · misc
- [Gallian2025Labeling]
A dynamic survey of graph labeling
Open ↗Joseph A. Gallian · 2025 · misc
The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.