Suggest a Book

# Complete balanced binary trees are graceful

Level: unknown

posted Jun 26 '12

Shiva Kintali
691 1 6 22
http://www.cs.princeton.e...

Label the vertices of a tree (with $n$ vertices) with integers from $1$ to $n$. Now label each edge with the absolute difference of the labels of its incident vertices. The labeling is said to be graceful if the edges are labeled $1$ through $n-1$ inclusive (with no number repeated). A tree is called graceful if it has at least one such labeling.

• Prove that every complete balanced binary tree is graceful.
Source: designed by Shiva Kintali
delete retag edit

## Stats

Posted: Jun 26 '12

Seen: 82 times

Last updated: Jun 26 '12