Problem Statement
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?
Categories:
Graph Theory Ramsey Theory
Progress
A problem of Erdős and Gyárfás. Gerencsér and Gyárfás [GeGy67] proved that, if the paths do not need to be of the same colour, then two paths suffice. Erdős and Gyárfás [ErGy95] proved that $2\sqrt{n}$ vertices suffice, and observed that $\sqrt{n}$ would be best possible here.Solved in the affirmative by Pokrovskiy, Versteegen, and Williams [PVW24].
Source: erdosproblems.com/518 | Last verified: January 15, 2026