Graceful Labeling of Spider Graphs With at Most Five Legs

A graceful labeling of a graph G with q edges is an injection f from the vertices of G to the set {0, 1, ⋯, q } such that, when each edge u v is assigned the label | f ( u ) − f ( v )|, the resulting edge labels are distinct. A spider graph is a tree with exactly one vertex of degree greater than 2, and this vertex is called the branch vertex. A leg of a spider graph is a path from the branch vertex to a leaf of the tree. We show that there exists graceful labeling of spider graphs with at most five legs.