Problem 550

Let $m_1\leq\cdots\leq m_k$ and $n$ be sufficiently large. If $T$ is a tree on $n$ vertices and $G$ is the complete multipartite graph with vertex class sizes $m_1,\ldots,m_k$ then prove that

R(T,G)\leq (\chi(G)-1)(R(T,K_{m_1,m_2})-1)+m_1.

Source: erdosproblems.com/550

Graph theory
Ramsey theory

Wiki page

Status

ClaimedProved

A full solution has been claimed but not yet accepted. The statement is true.

OPEN (LEAN), the site's label (no last-edited date shown); the frontmatter standing derives from the pending claim page Li 2026. A 2026 arXiv preprint (Li, arXiv:2606.23659; v1 22 June 2026, v2 2 August 2026) states the inequality as its Theorem 1.1 and claims a full proof; the author's proof claim on the site's proof-claim tab and the v2 listing report a Lean formalization. No refereed publication, independent review or acceptance by a named mathematician was found, and the site's discussion records reserved judgment. Before Li's claim the inequality was known in special cases: $k=2$ , where it is trivial since $m_1\ge1$ ; Chvátal's case $m_1=\dots=m_k=1$ for every $n$ ; a smallest class of size 1 for large $n$ (Erdős, Faudree, Rousseau and Schelp 1989, Theorem, p. 147); and trees of maximum degree at most $\Delta$ once $n$ is large in terms of $\Delta$ and the $m_i$ (their 1985 Theorem 1, p. 313, applied to both sides). The last three have partial claim pages: Chvátal 1977, Erdős, Faudree, Rousseau and Schelp 1989 and Erdős, Faudree, Rousseau and Schelp 1985. The community database set the formal status to Lean on 2026-09-18 (pull request 413, merged 17:28 UTC), pinning the author's repository at its head of 2 August 2026 with the note that the formalization was independently rebuilt from a clean clone (8,160 jobs; axioms propext, Classical.choice and Quot.sound only) and that the informal status stays open until a human reviews the paper; an archived snapshot of the site from the morning of 2026-09-18 still showed plain OPEN, so the label changed after that. The same day formal-conjectures tagged erdos_550 research solved ("solved (Li 2026)") and linked a formal proof (pull request 6080).

EFRS85: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., Multipartite graph--sparse graph Ramsey numbers. Combinatorica 5 (1985), no. 4, 311--318, doi:10.1007/BF02579245. The site's source key. Library home: Erdős 1985 (the Rényi archive's scan 1985-15.pdf; Theorem 1, p. 313; the Corollary and Theorem 3, p. 316; the questions of p. 317; the card carries the row for this problem). The paper does not state the problem's inequality.
EFRS89: Erdős, P., Faudree, R. J., Rousseau, C. C. and Schelp, R. H., Multipartite graph--tree Ramsey numbers. Graph theory and its applications: East and West (Jinan, 1986), Ann. New York Acad. Sci. 576 (1989), 146--154. Li (p. 2) locates the question as "(2) of [7, p. 153]", his [7] being this paper. Library home: Erdős 1989 (the Rényi archive's scan 1989-12.pdf; question (2), p. 153, and the Theorem of p. 147; the card quotes question (2) in full and carries the row for this problem).
Ch77: Chvátal, V., Tree-complete graph Ramsey numbers. J. Graph Theory 1 (1977), 93, doi:10.1002/jgt.3190010118. The one-page note proving $R(T,K_m)=(m-1)(n-1)+1$ . Not held. The statement is attested in [BuEr76] (p. 248, proof of Theorem 2.1) and in [Li26] p. 1.
Li26: Li, E., A resolution of Erdős Problem 550 on tree versus complete multipartite Ramsey numbers. arXiv:2606.23659 (v1 22 June 2026, 20 pp., the version cited; v2 2 August 2026, 26 pp., "The proof has been formally verified in Lean" per its listing, not held). Preprint. Theorem 1.1 and (3), p. 2; the acknowledgments, p. 20. Library home: Li 2026.
BuEr76: Burr, S. A. and Erdős, P., Extremal Ramsey theory for graphs. Utilitas Math. 9 (1976), 247--258; the proof of Theorem 2.1, p. 248, quotes Chvátal's theorem. Library home: Burr and Erdős 1976.

Problem 550

Status

Proof claims

Discussion