Problem 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$ ?

Source: erdosproblems.com/743

Graph theory

Wiki page

Status

Open

No claim settles this problem.

Falsifiable is the site's label; the conjecture is open, and that a single $n$ with a family of trees that does not pack would refute it is a note of the Current assessment, not a claim. No proof, disproof or accepted proof claim was found in the search whose scope the Current assessment records: the one arXiv proof claim (Chalise, Clark and Gnang, arXiv:2410.13840, 2024) was withdrawn by its authors on 1 September 2026, citing an error in the proof of their Composition Lemma 3.10 (claim page (Chalise Clark Gnang, 2024), withdrawn). The results that settle instances of the conjecture are recorded as partial claim pages, accepted or pending as their evidence allows, and with the withdrawn page they are the pages from which the frontmatter standing, open, is derived; no full claim is pending. What is proved: the conjecture for all large $n$ when the trees beyond the first $\varepsilon n$ have bounded maximum degree (Joos, Kim, Kühn and Osthus, Theorem 1.2, J. Eur. Math. Soc. 21 (2019), refereed; the accepted partial claim Joos, Kim, Kühn and Osthus 2016/2019), for all large $n$ when every tree has maximum degree at most $cn/\log n$ (Allen, Böttcher, Clemens, Hladký, Piguet and Taraz, Theorem 6, arXiv 2021--2026, a preprint with no journal record; the pending partial claim Allen, Böttcher, Clemens, Hladký, Piguet and Taraz 2021), for the largest $\varepsilon n$ trees of any degrees for every $n$ (Janzer and Montgomery, Theorem 1.2, arXiv v2 of April 2026, "accepted for publication" per its arXiv record), for the star and path families of Gyárfás and Lehel (a 1978 proceedings paper, not held; the pending partial claim Gyárfás and Lehel 1978), and by computer for every $n\le11$ (Guichard and Massman 1990, J. Combin. Math. Combin. Comput., the accepted partial claim Guichard and Massman 1990; Fishburn's $n\le9$ before it, J. Graph Theory 7 (1983), refereed, not held, the accepted partial claim Fishburn 1983). A forum computation of 8 September 2026 reports $n=12$ ; it is a lead. This is a bounded negative finding, not a certificate of openness.

JKKO19: Joos, Felix and Kim, Jaehoon and Kühn, Daniela and Osthus, Deryk, Optimal packings of bounded degree trees. J. Eur. Math. Soc. 21 (2019), no. 12, 3573--3647, doi:10.4171/JEMS/909 (issued 5 August 2019; Crossref record accessed). Paged in arXiv:1606.03953v2 (13 March 2019, 56 pp., "final version (December 2017)" per the arXiv record); Conjecture 1.1, p. 1; Theorem 1.2, p. 2. The journal text is not held; the page numbers are the arXiv version's. Library home: Joos et al. 2019; paged at Joos et al. 2019, Theorem 1.2 (p. 2).
ABCHPT21: Allen, Peter and Böttcher, Julia and Clemens, Dennis and Hladký, Jan and Piguet, Diana and Taraz, Anusch, The tree packing conjecture for trees of almost linear maximum degree. arXiv:2106.11720 (v1 22 June 2021; v2 20 June 2022, 157 pp., the version paged here; v3 8 September 2026, 179 pp., not held); no journal reference in the arXiv record. Conjecture 2, p. 3; Theorems 5--8, p. 5 (v2). Library home: Allen et al. 2021; paged at Allen et al. 2021, Theorem 6 (p. 5).
JaMo24: Janzer, Barnabás and Montgomery, Richard, Packing the largest trees in the tree packing conjecture. arXiv:2403.10515 (v1 15 March 2024; v2 9 April 2026, 34 pp., the version paged here, "Version accepted for publication", no journal named). Conjecture 1.1 and the history, p. 1; Theorem 1.2, p. 2. Library home: Janzer and Montgomery 2024; paged at Janzer and Montgomery 2024, Theorem 1.2 (p. 2).
GuMa90: Guichard, David R. and Massman, John D., A note on packing complete graphs with trees. J. Combin. Math. Combin. Comput. 8 (1990), 123--126 (zbMATH record 22649; no DOI). Not a site key; named in the thread on 27 August 2026. The note is open access on the publisher's site. Library home: Guichard and Massman 1990; paged at Guichard and Massman 1990, Verification (p. 124).
Fi83: Fishburn, P. C., Balanced integer arrays: a matrix packing theorem. J. Combin. Theory Ser. A 34 (1983), no. 1, 98--101, doi:10.1016/0097-3165(83)90045-6 (Crossref record accessed; text accessed). The site's key. Proposition 1, p. 98, with Graham's observation, p. 99: the degree sequences of $T_1,\ldots,T_n$ pack into that of $K_n$ (Graham's conjecture), as [JKKO19] (p. 1) and [GuMa90] (p. 123) cite it; the note states no result on the conjecture itself and no $n\le9$ verification. Library home: Fishburn 1983; paged at Fishburn 1983, Proposition 1.
Fi83b: Fishburn, P. C., Packing graphs with odd and even trees. J. Graph Theory 7 (1983), no. 3, 369--383, doi:10.1002/jgt.3190070309 (Crossref record accessed, whose abstract ends "The conjectures are also valid for all trees when $n\le9$ , so that the Gyárfás-Lehel conjecture holds for $n\le9$ "). Not held; not a site key; the paper [JaMo24] and [GuMa90] cite for the $n\le9$ verification.
GyLe78: Gyárfás, A. and Lehel, J., Packing trees of different order into $K_n$ . Combinatorics (Proc. Fifth Hungarian Colloq., Keszthely, 1976), Colloq. Math. Soc. János Bolyai 18, North-Holland (1978), 463--469 (as [GuMa90] and [ABCHPT21] cite it; the site's reference text gives no venue). Not held (print only; no attempt); its cases (all but at most two trees stars, or all stars or paths) are quoted from the site and [JaMo24]; [Bo83] (p. 203) attests the stars case.
Bo83: Bollobás, Béla, Some remarks on packing trees. Discrete Math. 46 (1983), no. 2, 203--204, doi:10.1016/0012-365X(83)90254-6 (Crossref and zbMATH records accessed; the publisher's open-archive license dated 2013; text accessed). The Theorem, p. 203; the Erdős--Sós remark, p. 204. Library home: Bollobás 1983; paged at Bollobás 1983, Theorem (p. 203).
CCG24: Chalise, Parikshit and Clark, Antwan and Gnang, Edinah K., A Proof of the Tree Packing Conjecture. arXiv:2410.13840 (v1 17 October 2024; v2 23 October 2024; v3 1 September 2026, withdrawn). A withdrawn claim, not a source (arXiv record); recorded as the claim page chalise_clark_gnang.
Er81: Erdős, P., On the combinatorial problems which I would most like to see solved. Combinatorica 1 (1981), no. 1, 25--42, doi:10.1007/BF02579174; p. 15 of the retyped copy, which has its own pagination. Library home: Erdős 1981.

Problem 743

Status

Proof claims

Discussion