SOLVED
This has been resolved in some other way than a proof or disproof.
Let $f(t)$ be minimal such that, in any two-colouring of the edges of $K_n$, the edges can be partitioned into vertex disjoint monochromatic copies of $K_t$ (not necessarily the same colour) with at most $f(t)$ vertices remaining.
Estimate $f(t)$. In particular, is it true that $f(t)^{1/t}\to 1$? Is it true that $f(t)\ll t$?
A question of Moon
[Mo66b], who proved that $f(3)=4$, at least for $n\geq 8$.
Presumably Erdős intended to only ask this question for $n$ sufficiently large depending on $t$. Erdős notes that $f(t)\ll 4^t$, by comparing to the Ramsey number $R(t)$.
Burr, Erdős, and Spencer
[BES75] proved that, for $n$ sufficiently large depending on $t$,\[f(t)=R(t,t-1)+x(t,n),\]where $0\leq x(t,n)<t$ is such that $n+1\equiv R(t,t-1)+x\pmod{t}$.
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1015, https://www.erdosproblems.com/1015, accessed 2026-01-16
