Another Equivalent of the Graceful Tree Conjecture

Abstract

Let $T=(V,E)$ be a tree on $|V|=n$ vertices. $T$ is graceful if there exists a bijection $f:V\to \{0,1,\dots ,n-1\}$ such that $\{|f(u)–f(v)|\mid uv\in E\}=\{1,2,\dots ,n-1\}$. If, moreover, $T$ contains a perfect matching $M$ and $f$ can be chosen in such a way that $f(u)+f(v)=n-1$ for every edge $uv\in M$ (implying that $\{|f(u)–f(v)|\mid uv\in M\}=\{1,3,\dots ,n-1\}$), then $T$ is called strongly graceful. We show that the well-known conjecture that all trees are graceful is equivalent to the conjecture that all trees containing a perfect matching are strongly graceful. We also give some applications of this result.