0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Can you clarify what you mean by "he absolute distance of labels of the vertices this edge is connecting, be distinct as well"? $\endgroup$ – Q the Platypus Mar 23 '16 at 5:57
  • $\begingroup$ 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. $\endgroup$ – gloomysunday Mar 23 '16 at 6:05
  • 1
    $\begingroup$ I don't think it's a theorem – I think it's the "Graceful Tree Conjecture", q.v. $\endgroup$ – Gerry Myerson Mar 23 '16 at 6:16
  • 1
    $\begingroup$ @GerryMyerson you're right. openproblemgarden.org/op/graceful_tree_conjecture it's a known open problem. $\endgroup$ – Q the Platypus Mar 23 '16 at 6:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.