  The Graceful Tree Conjecture of Rosa from 1967 asserts that the vertices of
each tree T of order n can be injectively labelled by using the numbers
{1,2,...,n} in such a way that the absolute differences induced on the edges
are pairwise distinct.
  We prove the following relaxation of the conjecture for each c>0 and for all
n>n_0(c). Suppose that (i) the maximum degree of T is bounded by O(n/log n),
and (ii) the vertex labels are chosen from the set {1,2,..., (1+c)n}. Then
there is an injective labelling of V(T) such that the absolute differences on
the edges are pairwise distinct. In particular, asymptotically almost all trees
on n vertices admit such a labelling.
  As a consequence, for any such tree T we can pack (2+2c)n-1 copies of T into
the complete graph of order (2+2c)n-1 cyclically. This proves an approximate
version of the Ringel-Kotzig conjecture (which asserts the existence of a
cyclic packing of 2n-1 copies of any T into the complete graph of order 2n-1)
for these trees.
  The proof proceeds by showing that a certain very natural randomized
algorithm produces a desired labelling with high probability.
