1 Graceful Labeling for Trees

We establish the existence of graceful labeling for any unlabeled tree by proposing actual construction procedure for such labeling. We define so called lattice and lattice paths sitting inside it. A lattice path is produced by starting with bottom (or top) row of the lattice and choosing one lattice point per row in the lattice in succession and joining these lattice points. With these lattice points we associate vertex pairs representing edges in a complete graph. It obviously follows that each of so called lattice path represents a graceful graph and further it easily follows that there exist in all n! graceful graphs (among which some are trees) in a complete graph on n vertices. In this paper we propose an algorithm to construct graceful labeling for any given unlabeled tree through construction of appropriate lattice path for this tree under consideration. 1. Introduction: