Graceful tree conjecture

Remarks

The conjecture is open. It is also called the Ringel–Kotzig conjecture. It is known for many families of trees, for example paths, stars and caterpillars, and computer searches have checked it for all trees with few vertices. A path $v_0 v_1 \cdots v_m$ has the graceful labeling $0, m, 1, m - 1, 2, \ldots$, with edge labels $m, m - 1, \ldots, 1$. Rosa showed that a graceful labeling of a tree $T$ with $m$ edges gives a decomposition of the complete graph $K_{2m+1}$ into $2m + 1$ copies of $T$. So the conjecture would imply Ringel's conjecture on such decompositions. Ringel's conjecture was proved for all large $m$ by Montgomery, Pokrovskiy and Sudakov, by other methods. Not every graph is graceful: for example the cycle $C_n$ has a graceful labeling only when $n \equiv 0$ or $3 \pmod 4$.