Show that any tree $T$ on $n$ vertices with a k-graceful labeling also has 3n-graceful coloring. A k-graceful labeling of a tree T on n vertices is a 1-1 mapping $f: V(T) \to \{1,...,k\}$ so that the numbers $|f(x)-f(y)|$ computed across edges $xy \in E(T)$ are all distinct. Show that any such tree has a 3n-graceful coloring. Is it possible to do any better?
I guess I'm confused if k is necessarily larger than n. Right now my starting point is to assign prime numbers to the vertices, but I'm not sure if that's the right way to go about this proof.
EDIT:
Now I'm thinking of just assigning numbers of increasing difference to each vertex?
 A: I believe I've figured it out.
The first step is to find the longest simple path in tree $T$.
It has a k-graceful labeling where k is the length of the path, and can be labeled using the following algorithm:
$$1 \to k \to 2 \to (k-1) \to 3 \to (k-2) \to etc...$$
For example, if the longest path has length k=5, then the labeling would be:
$$1 \to 5 \to 2 \to 3 \to 4$$
Clearly, the values of $|f(x)-f(y)|$ for $xy \in E(T)$ are all distinct, and have the values $\{1,2,3,4\}$
In general, the values of $|f(x)-f(y)|$ that have been taken at this point are $\{1,...,k-1\}$, and of the $[3n]$ potential labels we could have used, we have used the first $[k]$ of them, leaving $3n-(k+1)$ labels to choose from to apply to the remaining $n-k$ vertices.
The remaining $n-k$ labels can be applied using the following algorithm:
Apply the largest label possible to the neighbor with the smallest label
There will be no way a duplicate value of $|f(x)-f(y)|$ can be generated because each successive difference will be smaller than the next, and no difference will equal the first $[k-1]$ $|f(x)-f(y)|$ values because the largest remaining labels are at least $2n$ away from any of the original $k$ labels, and we only need to use $(n-k)/2$ of them with the algorithm described.
Therefore, a 3n-graceful coloring can be found for any tree $T$.
Let me know if my logic isn't sound.
