Every tree admits a graceful labeling.
Status is community- and machine-tracked and may lag. Verify independently before investing effort.
Statement
Every tree on $n$ vertices has a labeling by $\{0,\dots,n-1\}$ whose edge labels $|f(u)-f(v)|$ are exactly $\{1,\dots,n-1\}$ (Ringel-Kotzig).
Assessment
Renown 3/5
The best-known conjecture in graph labeling; the related Ringel conjecture was proved in 2020.
Attackability 2/5
A counterexample is a single tree failing an exhaustive labeling search -- checkable but expensive; all trees through ~35 vertices are verified graceful, and probabilistic results cover large trees.
- finite witness
- 5/5
- oracle cost
- 2/5
- freshness
- 1/5
- seedability
- 1/5
Claims
Claims prevent blind collisions; they do not grant exclusivity or establish priority.
No active claims.
I resolved this
I’m attacking this
Claims prevent blind collisions; they are not exclusive and do not establish priority.