# Labeling a tree, a theorem

Can you help me in proving this theorem?

Theorem: If we have a tree with n vertices, we can label each vertex with distinct labels chosen from the set $\{1,2,3,\dots,n\}$, so that after this labeling, for each chosen edge $(i,j),$ the absolute distance of labels of the vertices this edge is connecting, be distinct as well.

• Can you clarify what you mean by "he absolute distance of labels of the vertices this edge is connecting, be distinct as well"? – Q the Platypus Mar 23 '16 at 5:57
• Each edge, is connecting two vertices with labels i and j, i mean, if for all the edges, we gather the |i-j|s, these values are all different. – gloomysunday Mar 23 '16 at 6:05
• I don't think it's a theorem – I think it's the "Graceful Tree Conjecture", q.v. – Gerry Myerson Mar 23 '16 at 6:16
• @GerryMyerson you're right. openproblemgarden.org/op/graceful_tree_conjecture it's a known open problem. – Q the Platypus Mar 23 '16 at 6:22