$4$-graceful trees

Let $f$ be a coloring of the vertices of a connected graph $G$ into colors from a set $\{1, 2, \dots, k\}$. The coloring $f$ induces on the set of edges of $G$ a function $f'(e) = |f(u) - f(v)|$, where $e = uv$ is an arbitrary edge of $G$. The integer $f'(e)$ will be called the color of the edge $e$ induced by the coloring $f$. The coloring $f$ is called a graceful $k$-coloring of $G$ if $f'$ is an edge coloring of this graph. We will call a graph $k$-graceful or, simply, graceful if it has a graceful $k$-coloring. The main goal of our work is to give two sufficient conditions, each of which guarantees the 4-gracefulness of trees (see Theorems 1 and 2). In addition, we study the properties of 4-graceful graphs to prove these theorems. We also plan to use the found properties in the subsequent works on 4-graceful graphs and 4-graceful trees in the general case. Let us note that the 4-graceful trees are quite complex, while the 3-graceful connected graphs have a very simple structure. The latter are limited to simple chains of length at most 3. It is easy to establish that any 4-graceful graph does not contain vertices of degree greater than 3. Therefore, we consider trees $T$ whose vertex degrees do not exceed 3. We will call vertices of degree 3 in a tree $T$ nodes. For two nodes $u$ and $v$ of a tree $T$, we will say that the nodal distance between them is $t$ if there is a simple chain from $u$ to $v$ such that the number of internal vertices of this chain is $t\geq 1$ and all these internal vertices have degree 2 in the tree $T$. Of course, the nodal distance is not always defined for a pair of nodes. Among other properties of 4-graceful graphs, it established that such graphs do not contain simple chains consisting of three nodes. The sufficient conditions for 4-gracefulness formulated in the paper consist in prohibiting the appearance in trees of pairs of nodes whose nodal distances are equal to 1 or 2.