Star Graph

The $k$-star graph is a Tree on $k+1$ nodes with one node having valency $k$ and the others having valency 1. Star graphs $S_n$ are always Graceful.