Problem #544: Show that\[R(3,k+1)-R(3,k)\to\infty\]as $k\to \infty$

Show that\[R(3,k+1)-R(3,k)\to\infty\]as $k\to \infty$. Similarly, prove or disprove that\[R(3,k+1)-R(3,k)=o(k).\]

SOLVED

Problem Statement

Show that\[R(3,k+1)-R(3,k)\to\infty\]as $k\to \infty$. Similarly, prove or disprove that\[R(3,k+1)-R(3,k)=o(k).\]

Categories: Graph Theory Ramsey Theory

A problem of Erdős and Sós.

This problem is #8 in Ramsey Theory in the graphs problem collection.

See also [165] and [1014].

Source: erdosproblems.com/544 | Last verified: January 15, 2026