An $n$-vertex tree $T$ is said to be $\textit{ graceful}$ if there exists a bijective labelling $\phi:V(T)\to \{ 1,\ldots,n\}$ such that the edge-differences $\{ |\phi(x)-\phi(y)| : xy\in E(T)\}$ are pairwise distinct. The longstanding graceful tree conjecture, posed by R\'{ o}sa in the 1960s, asserts that every tree is graceful. The $\textit{ gracesize}$ of an $n$-vertex tree $T$, denoted $\operatorname{ gs}(T)$, is the maximum possible number of distinct edge-differences over all bijective labellings $\phi:V(T)\to \{ 1,\ldots,n\}$. The graceful tree conjecture is therefore equivalent to the statement that $\operatorname{ gs}(T)=n-1$ for all $n$-vertex trees. We prove an asymptotic version of this conjecture by showing that for every $\varepsilon>0$, there exists $n_0$ such that every tree on $n>n_0$ vertices satisfies $\operatorname{ gs}(T)\geqslant (1-\varepsilon)n$. In other words, every sufficiently large tree admits an almost graceful labelling.
Categories: math.CO