Problem 518

Is it true that, in any two-colouring of the edges of $K_n$ , there exist $\sqrt{n}$ monochromatic paths, all of the same colour, which cover all vertices?

Source: erdosproblems.com/518

Graph theory
Ramsey theory

Wiki page

Status

ClaimedProved

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

The site labels the problem PROVED and its curator credits Pokrovskiy, Versteegen and Williams with the affirmative answer. The credited result is Theorem 1.3 of their paper (J. Combin. Theory Ser. B 176 (2026), 551--560, refereed; the statement here follows arXiv v2 of 7 October 2025), which states the conclusion for all $n>20^{40}$ . For $n\le20^{40}$ the paper proves only its Proposition 3.4 (p. 7), that fewer than $\sqrt n+20^4$ monochromatic paths of one color always suffice (its remark that $\sqrt n+10$ paths suffice for every $n$ is announced "with some additional technical effort", not proved), and the statement for every $n\ge1$ is claimed in an unrefereed 2026 preprint of Chen and Chen, the one entry of the site's proof-claims tab, which the site has not adopted. The claim pages Pokrovskiy, Versteegen and Williams 2024 (accepted on the site's credit and the refereed publication, partial: every $n>20^{40}$ ) and Chen and Chen 2026 (claimed, the statement for every $n$ ) record the results, their postings and their acceptance evidence, and the frontmatter standing derives from them: the problem stands as claimed through the pending full claim, while the site's label rests on the large- $n$ theorem, read here as settling the question for large $n$ only. No review of the proof is recorded.

ErGy95: Erdős, P. and Gyárfás, A., Vertex covering with monochromatic paths. Math. Pannon. 6 (1995), no. 1, 7--10 (received October 1994). The Theorem, p. 8; Corollary 2 and Problem 2, p. 10. Library home: Erdős and Gyárfás 1995.
GeGy67: Gerencsér, L. and Gyárfás, A., On Ramsey-type problems. Ann. Univ. Sci. Budapest. Eötvös Sect. Math. 10 (1967), 167--170 (received 10 February 1966). Theorem 1, p. 168; the two-path remark, footnote 1 on p. 169. The four pages are in the journal's archive scan of the volume (annalesm.elte.hu). Library home: Gerencsér and Gyárfás 1967.
PVW24: Pokrovskiy, A., Versteegen, L. and Williams, E., A proof of a conjecture of Erdős and Gyárfás on monochromatic path covers. J. Combin. Theory Ser. B 176 (2026), 551--560, doi:10.1016/j.jctb.2025.10.007; arXiv:2409.03623 (v1 5 September 2024; v2 7 October 2025, 8 pages). Theorems 1.1--1.3 and the construction, pp. 1--2 of the preprint. Library home: Pokrovskiy and Williams 2024.
ChCh26: Chen, H. and Chen, Y., On monochromatic path covers conjecture of Erdős--Gyárfás. arXiv:2607.21915v1 (24 July 2026), 14 pages; an unrefereed preprint. Theorem 1.5, p. 2. Library home: Chen and Chen 2026.
Gy16: Gyárfás, A., Vertex covers by monochromatic pieces---a survey of results and problems. Discrete Math. 339 (2016), 1970--1977. The source [PVW24] cites for the conjecture's attribution; not held.
GyLe73: Gyárfás, A. and Lehel, J., A Ramsey-type problem in directed and bipartite graphs. Period. Math. Hungar. 3 (1973), 299--304. The bipartite path lemma [PVW24] uses (its Lemma 2.1); not held.
LTY26: Liu, X.-C., Teodomiro, J. and Yang, X., Sharp same-color cycle covers in two-colored complete graphs. arXiv:2608.27331v1 (27 August 2026); abstract only: $\lceil\sqrt n\rceil$ monochromatic cycles of one color cover the vertex set for all $n$ . Context, the cycle variant.
EuMo17: Eugster, M. and Mousset, F., Vertex covering with monochromatic pieces of few colours. arXiv:1711.01557v2; Electron. J. Combin. 25 (2018) per [PVW24]. Abstract only; context, the $r$ -color, $s$ -color variant.

Problem 518

Status

Proof claims

Discussion