March 28, 2009 2:00 am

Caterpillar graphs are graceful

Let T(V,E) be a tree, with |V|=n. A graceful labeling of T is an assignment of labels (from 1 to n) to the vertices such that if the edges are labeled with the absolute difference of their incident vertices, then each edge receives a unique label (i.e., each of the n-1 edges receive labels fron 1 to n-1). It is easy to see that stars and paths are graceful.

A caterpillar graph is a tree such that if all leaves and their incident edges are removed, the remainder of the graph forms a path. Here’s a cute problem :

• Prove that all caterpillar graphs are graceful

Hint : Given a graceful labeling find another labeling with a special property and apply induction.

Have fun solving this. I almost gave you the solution.