Erdős Problem #743

Erdős Problem 743 --- collection record

PROVENANCE AND STATUS

Official problem: https://www.erdosproblems.com/743

Saved collaborative-database status: falsifiable. Snapshot checked: 2026-09-23T17:22:24Z. Latest status and formalization links: https://teorth.github.io/erdosproblems/

This is an attributed collection of existing writeups. The model-folder names below identify their original attribution; placement in GPT_6_Astra_Ultra does not attribute their mathematical work to that model. All locally available source versions selected for this problem are reproduced below, without editing their text.

Proof claims, computations, literature statements, and completion estimates in the reused text have not been independently verified in this collection pass. A source claiming a solution does not change the saved upstream status.

Primary source (latest numbered version in the preferred model folder): attacks/erdos/gpt_pro_5.2/743.tex.

REUSED SOURCE 1

Original attribution: gpt_pro_5.2. Original file: attacks/erdos/gpt_pro_5.2/743.tex.

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. Gyárfás and Lehel [GyLe78] proved that this holds if all but at most $2$ of the trees are stars, or if all the trees are stars or paths. Fishburn [Fi83] proved this for $n\leq 9$. Bollobás [Bo83] proved that the smallest $\lfloor n/\sqrt{2}\rfloor$ many trees can always be packed greedily into $K_n$. Joos, Kim, Kühn, and Osthus [JKKO19] proved that this conjecture holds when the trees have bounded maximum degree. Allen, Böttcher, Clemens, Hladky, Piguet, and Taraz [ABCHPT21] proved that this conjecture holds when all the trees have maximum degree $\leq c\frac{n}{\log n}$ for some constant $c>0$. Janzer and Montgomery [JaMo24] have proved that there exists some $c>0$ such that the largest $cn$ trees can be packed into $K_n$. References [ABCHPT21] Allen, Peter and Böttcher, Julia and Clemens, Dennis and Hladky, J. and D. Piguet and Taraz, Anusch, The tree packing conjecture for trees of almost linear maximum degree . arXiv:2106.11720 $2021$. [Bo83] Bollobás, Béla, Some remarks on packing trees . Discrete Math. $1983$, 203-204. [Fi83] Fishburn, P. C., Balanced integer arrays: a matrix packing theorem . J. Combin. Theory Ser. A $1983$, 98-101. [GyLe78] Gyárfás, A. and Lehel, J., Packing trees of different order into {$K\sb{n}$} . $1978$, 463-469. [JKKO19] Joos, Felix and Kim, Jaehoon and Kühn, Daniela and Osthus, Deryk, Optimal packings of bounded degree trees . J. Eur. Math. Soc. (JEMS) $2019$, 3573-3647. [JaMo24] Janzer, B. and R. Montgomery, Packing the largest trees in the tree packing conjecture . arXiv:2403.10515 $2024$.

1) FORMAL RESTATEMENT.

Fix an integer $n\ge 2$. Let $T_2,\dots,T_n$ be trees (simple graphs) such that $|V(T_k)|=k$ for each $k\in\{2,\dots,n\}$.

We ask whether for every such collection there exist injective maps \[\varphi_k:V(T_k)\hookrightarrow [n]\] so that the image edge sets \[\varphi_k(E(T_k)):=\{\{\varphi_k(u),\varphi_k(v)\}:\{u,v\}\in E(T_k)\} \subseteq E(K_n) \] are pairwise disjoint and their union equals $E(K_n)$.

Equivalently: can $K_n$ be decomposed into edge-disjoint subgraphs isomorphic to $T_k$ for $k=2,\dots,n$?

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement lists multiple partial results (special families of trees, small $n$, bounded degree, etc.). I do not use any external results beyond what is explicitly stated there; in particular, below I give an explicit proof for the "all stars" special case and an exhaustive computational sanity check for $n\le 8$.

3) ATTACK PLAN.

Proof-track ideas.

• Induction on $n$ by embedding the largest tree $T_n$ and then decomposing the leftover graph into the remaining trees (hard because the leftover graph need not be complete).
• Explicit constructions for restricted families (stars, paths) as base cases.

Disproof-track ideas.

• Try to construct a collection of trees whose degree constraints force too many edges incident to a single vertex, preventing an edge-disjoint embedding.

In this write-up: prove two basic structural lemmas and provide exhaustive checks for small $n$.

4) WORK.

Fast reality check (computation). I exhaustively verified the conjectured packing property for all choices of trees up to isomorphism for $n\le 8$.

• For each $k$, I generated all nonisomorphic trees on $k$ vertices (counts: $1,1,2,3,6,11,23$ for $k=2,3,4,5,6,7,8$).
• For each sequence $(T_2,\dots,T_n)$ of such types (there are $1,1,2,6,36,396,9108$ sequences for $n=2,3,4,5,6,7,8$), I used backtracking to search for edge-disjoint embeddings into $K_n$.
• Result: every sequence for $n\le 8$ admitted a packing (no counterexample found).

Lemma 743.1 (Edge count matches exactly). For any $n\ge 2$, \[ \sum_{k=2}^n |E(T_k)| = \sum_{k=2}^n (k-1) = \frac{n(n-1)}{2} = |E(K_n)|. \] In particular, if the $T_k$ can be embedded edge-disjointly into $K_n$, then they necessarily form a decomposition of $K_n$ (no leftover edges).

Proof. A tree on $k$ vertices has exactly $k-1$ edges. Hence \[ \sum_{k=2}^n |E(T_k)|=\sum_{k=2}^n (k-1)=\sum_{j=1}^{n-1} j = \frac{(n-1)n}{2}. \] Also $K_n$ has $\binom{n}{2}=n(n-1)/2$ edges, giving the claimed equality. $\square$

Lemma 743.2 (Explicit packing when all $T_k$ are stars). Suppose for each $k\in\{2,\dots,n\}$, the tree $T_k$ is a star on $k$ vertices (i.e., $K_{1,k-1}$). Then $K_n$ can be written as an edge-disjoint union of the $T_k$.

Proof. Label the vertices of $K_n$ as $1,2,\dots,n$. For each $k\in\{2,\dots,n\}$, define a star subgraph $S_k$ centered at vertex $k$ with leaf set $\{1,2,\dots,k-1\}$, i.e. \[ E(S_k)=\{\{k,i\}: 1\le i\le k-1\}. \] Then $S_k$ has $k-1$ edges and is isomorphic to $K_{1,k-1}$.

The edge sets $E(S_k)$ are pairwise disjoint: if an edge $\{a,b\}$ has $a<b$, then it appears exactly in $E(S_b)$ and in no other $E(S_k)$.

Finally, every edge $\{a,b\}$ of $K_n$ with $a<b$ belongs to $E(S_b)$, so the union of these stars covers all edges. Thus the $S_k$ form an edge-disjoint decomposition of $K_n$ into the desired stars. $\square$

5) VERIFICATION.

• Lemma 743.1: checked the arithmetic sum $\sum_{j=1}^{n-1} j=n(n-1)/2$.
• Lemma 743.2: verified disjointness carefully by unique assignment of edge $\{a,b\}$ to the star centered at $\max\{a,b\}$.
• Computation: the search explicitly constructed embeddings, so a reported "True" means a certificate packing exists for that instance.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result: a complete explicit construction when all trees are stars (Lemma 743.2), plus exhaustive verification for all isomorphism-type sequences for $n\le 8$.

(ii) First gap: prove (or disprove via an explicit counterexample) that for every $n$ and every collection of trees $T_2,\dots,T_n$ with $|V(T_k)|=k$, there is an edge-disjoint packing into $K_n$.

(iii) Top 3 next moves:

1. Attempt an induction scheme that embeds the largest tree $T_n$ in a way that leaves a highly structured remainder graph (e.g., with large minimum degree), enabling recursive packing of $T_2,\dots,T_{n-1}$.
2. Develop a robust greedy/random embedding lemma for packing $T_n,T_{n-1},\dots$ while maintaining quasirandomness of unused edges.
3. Search computationally for small counterexample structures by restricting to "extremal" tree shapes (e.g., high maximum degree vs. long paths) and testing $n=9,10,\dots$ beyond exhaustive limits.

(iv) Minimal counterexample structure (if false): a smallest $n$ and a sequence $T_2,\dots,T_n$ such that no decomposition exists. By minimality, every proper subsequence would pack in the corresponding smaller complete graph. Such a counterexample would likely involve a few trees forcing many edges incident to the same vertex in any embedding (degree-saturation obstruction).

COMPLETION ESTIMATE

The primary source supplies no extractable numerical completion estimate. Its mathematical progress is not numerically assessed here.

Newly verified progress in this collection pass: $0\%$. This measures new verification work, not the amount of mathematics achieved in the reused text.

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. Gyárfás and Lehel [GyLe78] proved that this holds if all but at most $2$ of the trees are stars, or if all the trees are stars or paths. Fishburn [Fi83] proved this for $n\leq 9$. Bollobás [Bo83] proved that the smallest $\lfloor n/\sqrt{2}\rfloor$ many trees can always be packed greedily into $K_n$. Joos, Kim, Kühn, and Osthus [JKKO19] proved that this conjecture holds when the trees have bounded maximum degree. Allen, Böttcher, Clemens, Hladky, Piguet, and Taraz [ABCHPT21] proved that this conjecture holds when all the trees have maximum degree $\leq c\frac{n}{\log n}$ for some constant $c>0$. Janzer and Montgomery [JaMo24] have proved that there exists some $c>0$ such that the largest $cn$ trees can be packed into $K_n$. References [ABCHPT21] Allen, Peter and Böttcher, Julia and Clemens, Dennis and Hladky, J. and D. Piguet and Taraz, Anusch, The tree packing conjecture for trees of almost linear maximum degree . arXiv:2106.11720 $2021$. [Bo83] Bollobás, Béla, Some remarks on packing trees . Discrete Math. $1983$, 203-204. [Fi83] Fishburn, P. C., Balanced integer arrays: a matrix packing theorem . J. Combin. Theory Ser. A $1983$, 98-101. [GyLe78] Gyárfás, A. and Lehel, J., Packing trees of different order into {$K\sb{n}$} . $1978$, 463-469. [JKKO19] Joos, Felix and Kim, Jaehoon and Kühn, Daniela and Osthus, Deryk, Optimal packings of bounded degree trees . J. Eur. Math. Soc. (JEMS) $2019$, 3573-3647. [JaMo24] Janzer, B. and R. Montgomery, Packing the largest trees in the tree packing conjecture . arXiv:2403.10515 $2024$.

1) FORMAL RESTATEMENT.

Fix an integer $n\ge 2$. Let $T_2,\dots,T_n$ be trees (simple graphs) such that $|V(T_k)|=k$ for each $k\in\{2,\dots,n\}$.

We ask whether for every such collection there exist injective maps \[\varphi_k:V(T_k)\hookrightarrow [n]\] so that the image edge sets \[\varphi_k(E(T_k)):=\{\{\varphi_k(u),\varphi_k(v)\}:\{u,v\}\in E(T_k)\} \subseteq E(K_n) \] are pairwise disjoint and their union equals $E(K_n)$.

Equivalently: can $K_n$ be decomposed into edge-disjoint subgraphs isomorphic to $T_k$ for $k=2,\dots,n$?

2) QUICK LITERATURE/CONTEXT CHECK.

The problem statement lists multiple partial results (special families of trees, small $n$, bounded degree, etc.). I do not use any external results beyond what is explicitly stated there; in particular, below I give an explicit proof for the "all stars" special case and an exhaustive computational sanity check for $n\le 8$.

3) ATTACK PLAN.

Proof-track ideas.

• Induction on $n$ by embedding the largest tree $T_n$ and then decomposing the leftover graph into the remaining trees (hard because the leftover graph need not be complete).
• Explicit constructions for restricted families (stars, paths) as base cases.

Disproof-track ideas.

• Try to construct a collection of trees whose degree constraints force too many edges incident to a single vertex, preventing an edge-disjoint embedding.

In this write-up: prove two basic structural lemmas and provide exhaustive checks for small $n$.

4) WORK.

Fast reality check (computation). I exhaustively verified the conjectured packing property for all choices of trees up to isomorphism for $n\le 8$.

• For each $k$, I generated all nonisomorphic trees on $k$ vertices (counts: $1,1,2,3,6,11,23$ for $k=2,3,4,5,6,7,8$).
• For each sequence $(T_2,\dots,T_n)$ of such types (there are $1,1,2,6,36,396,9108$ sequences for $n=2,3,4,5,6,7,8$), I used backtracking to search for edge-disjoint embeddings into $K_n$.
• Result: every sequence for $n\le 8$ admitted a packing (no counterexample found).

Lemma 743.1 (Edge count matches exactly). For any $n\ge 2$, \[ \sum_{k=2}^n |E(T_k)| = \sum_{k=2}^n (k-1) = \frac{n(n-1)}{2} = |E(K_n)|. \] In particular, if the $T_k$ can be embedded edge-disjointly into $K_n$, then they necessarily form a decomposition of $K_n$ (no leftover edges).

Proof. A tree on $k$ vertices has exactly $k-1$ edges. Hence \[ \sum_{k=2}^n |E(T_k)|=\sum_{k=2}^n (k-1)=\sum_{j=1}^{n-1} j = \frac{(n-1)n}{2}. \] Also $K_n$ has $\binom{n}{2}=n(n-1)/2$ edges, giving the claimed equality. $\square$

Lemma 743.2 (Explicit packing when all $T_k$ are stars). Suppose for each $k\in\{2,\dots,n\}$, the tree $T_k$ is a star on $k$ vertices (i.e., $K_{1,k-1}$). Then $K_n$ can be written as an edge-disjoint union of the $T_k$.

Proof. Label the vertices of $K_n$ as $1,2,\dots,n$. For each $k\in\{2,\dots,n\}$, define a star subgraph $S_k$ centered at vertex $k$ with leaf set $\{1,2,\dots,k-1\}$, i.e. \[ E(S_k)=\{\{k,i\}: 1\le i\le k-1\}. \] Then $S_k$ has $k-1$ edges and is isomorphic to $K_{1,k-1}$.

The edge sets $E(S_k)$ are pairwise disjoint: if an edge $\{a,b\}$ has $a<b$, then it appears exactly in $E(S_b)$ and in no other $E(S_k)$.

Finally, every edge $\{a,b\}$ of $K_n$ with $a<b$ belongs to $E(S_b)$, so the union of these stars covers all edges. Thus the $S_k$ form an edge-disjoint decomposition of $K_n$ into the desired stars. $\square$

5) VERIFICATION.

• Lemma 743.1: checked the arithmetic sum $\sum_{j=1}^{n-1} j=n(n-1)/2$.
• Lemma 743.2: verified disjointness carefully by unique assignment of edge $\{a,b\}$ to the star centered at $\max\{a,b\}$.
• Computation: the search explicitly constructed embeddings, so a reported "True" means a certificate packing exists for that instance.

6) FINAL. UNRESOLVED

(i) Strongest proved partial result: a complete explicit construction when all trees are stars (Lemma 743.2), plus exhaustive verification for all isomorphism-type sequences for $n\le 8$.

(ii) First gap: prove (or disprove via an explicit counterexample) that for every $n$ and every collection of trees $T_2,\dots,T_n$ with $|V(T_k)|=k$, there is an edge-disjoint packing into $K_n$.

(iii) Top 3 next moves:

1. Attempt an induction scheme that embeds the largest tree $T_n$ in a way that leaves a highly structured remainder graph (e.g., with large minimum degree), enabling recursive packing of $T_2,\dots,T_{n-1}$.
2. Develop a robust greedy/random embedding lemma for packing $T_n,T_{n-1},\dots$ while maintaining quasirandomness of unused edges.
3. Search computationally for small counterexample structures by restricting to "extremal" tree shapes (e.g., high maximum degree vs. long paths) and testing $n=9,10,\dots$ beyond exhaustive limits.

(iv) Minimal counterexample structure (if false): a smallest $n$ and a sequence $T_2,\dots,T_n$ such that no decomposition exists. By minimality, every proper subsequence would pack in the corresponding smaller complete graph. Such a counterexample would likely involve a few trees forcing many edges incident to the same vertex in any embedding (degree-saturation obstruction).