Every tree on $n$ edges decomposes $K_{nx,nx}$ and $K_{2nx+1}$

Abstract

We prove that every tree on $n$ edges decomposes $K_{nx,nx}$ and $K_{2nx+1}$ for all positive integers $x$. The said decompositions are obtained by proving that every tree admits a $\vec{\beta }$-labeling (oriented beta-labeling). Our proof employs the polynomial method by identifying trees as functions in the transformation monoid ${\mathbb{Z}}_n^{{\mathbb{Z}}_n}$. A proof of the graceful tree conjecture (1967) follows as an immediate consequence of the current result. Finally, we introduce additional algebraic properties derived from the decomposition results.

Withdrawn due to an error in the proof of Lemma 4.3 (Composition Lemma), which was based on the argument in arXiv:2202.03178v2