On the gracesize of trees

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