TOPICS
Search

Tree Packing Conjecture

The tree packing conjecture of Gyárfás and Lehel (1978) asserts that for any trees T_1,...,T_n with T_i having i vertices, there are pairwise edge-disjoint copies of all the trees in the complete graph K_n. Their total number of edges is

sum_(i=1)^n(i-1)=n2,

so such a packing is an exact partition of the edges of K_n.

The general conjecture remains open. Janzer and Montgomery (2026) proved that there is an absolute constant c>0 such that the largest cn trees can be packed for all sufficiently large n.

This is problem 743 in the Erdős problems collection (Bloom 2026).

See also

Complete Graph, Erdős Problems, Tree

Explore with Wolfram|Alpha

References

Bloom, T. F. "Erdős Problem 743." Accessed Oct. 26, 2026. https://www.erdosproblems.com/743.Gyárfás, A. and Lehel, J. "Packing Trees of Different Order into K_n." In Combinatorics, Vol. I (Proc. Fifth Hungarian Colloq., Keszthely, 1976) (Ed. A. Hajnal and V. T. Sós). Amsterdam, Netherlands: North-Holland, pp. 463-469, 1978.Janzer, B. and Montgomery, R. "Packing the Largest Trees in the Tree Packing Conjecture." J. Eur. Math. Soc., in press, 2026. https://doi.org/10.4171/JEMS/1794.

Cite this as:

Weisstein, Eric W. "Tree Packing Conjecture." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/TreePackingConjecture.html

Subject classifications