Graceful Labeling : Label the vertices of a simple undirected graph $G(V,E)$ (where $|V| = n$ and $|E| = m$) with integers from $0$ to $m$. 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 $m$ inclusive (with no number repeated). A graph is called graceful if it has at least one such labeling.
[Easy] : Prove that every graceful graph has at least two graceful labelings.
[Easy] : Prove that stars, paths are graceful.
Prove that all caterpillar graphs are graceful.
Posted: Jun 07 '12
Seen: 98 times
Last updated: Oct 24 '12
