Erdős Problem 743: erdos_743

Let $T_2,\ldots,T_n$ be a collection of trees such that $T_k$ has $k$ vertices. Can we always write $K_n$ as the edge disjoint union of the $T_k$?

A conjecture of Gyárfás, known as the tree packing conjecture. We state it as a packing. For every $n$ and all trees $T_k$ on the vertex set Fin k, $2 \leq k \leq n$, there are injective maps $f_k : \{0, \ldots, k - 1\} \to \{0, \ldots, n - 1\}$ such that the graphs $f_k(T_k)$ are pairwise edge-disjoint (see IsPacking). Every tree with $k$ vertices is isomorphic to a tree on Fin k, so this covers every collection of trees.

A tree with $k$ vertices has $k - 1$ edges, and $\sum_{k=2}^{n} (k - 1) = \binom{n}{2}$ is the number of edges of $K_n$. Hence the copies $f_k(T_k)$ of a packing cover every edge of $K_n$. So a packing is the same as a decomposition of $K_n$ into copies of $T_2, \ldots, T_n$.