A Proof of the Tree Packing Conjecture

Abstract

We prove a conjecture of Gyárfás (1976), which asserts that any family of trees $T_1,\dots ,T_n$ where each $T_k$ has $k$ vertices packs into $K_n$. We do so by translating the decomposition problem into a labeling problem, namely complete labeling. Our proof employs the polynomial method using a functional reformulation of the conjecture.

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