Problem #800: If $G$ is a graph on $n$ vertices which has no two adjacent...

If $G$ is a graph on $n$ vertices which has no two adjacent vertices of degree $\geq 3$ then\[R(G)\ll n,\]where the implied constant is absolute.

SOLVED

Problem Statement

If $G$ is a graph on $n$ vertices which has no two adjacent vertices of degree $\geq 3$ then\[R(G)\ll n,\]where the implied constant is absolute.

Categories: Graph Theory Ramsey Theory

A problem of Burr and Erdős. Solved in the affirmative by Alon [Al94]. This is a special case of [163].

Source: erdosproblems.com/800 | Last verified: January 16, 2026