Any Tree with mm edges can be embedded in a Graceful Tree with less than 4m4m edges and in a graceful planar graph

A function ff is called a graceful labeling of a graph GG with mm edges, if ff is an injective function from V(G)V(G) to {0,1,2,…,m}{0,1,2,…,m} such that when every edge uvuv is assigned the edge label |f(u)−f(v)||f(u)−f(v)|, then the resulting edge labels are distinct. A graph which admits a graceful labeling is called a graceful graph. In this paper, we prove a basic structural property of graceful graphs, that every tree can be embedded as a spanning subtree in a graceful planar graph. Also we show that any tree with mm edges can be embedded in a graceful tree with less than 4m4m edges. A range-relaxed graceful labeling ff is defined from V(G)V(G) to 0,1,2,…,m′0,1,2,…,m′, where m′≥mm′≥m. We improve the bound 2m−diam(T)2m−diam(T) on the range-relaxed graceful labeling given by Van Bussel (2002) for a tree TT.