Problem Statement
Let $G$ be a graph with $m$ edges and no isolated vertices. Is the Ramsey number $R(G)$ maximised when $G$ is 'as complete as possible'? That is, if $m=\binom{n}{2}+t$ edges with $0\leq t<n$ then is\[R(G)\leq R(H),\]where $H$ is the graph formed by connecting a new vertex to $t$ of the vertices of $K_n$?
Categories:
Graph Theory Ramsey Theory
Progress
A question of Erdős and Graham. The weaker question of whether\[R(G) \leq 2^{O(m^{1/2})}\]is the subject of [546]. (This is true, and was proved by Sudakov [Su11].)LouisD in the comments has noted this fails for small $m$ (in particular for $2\leq m\leq 5$ and $7\leq m\leq 9$).
This problem is #10 in Ramsey Theory in the graphs problem collection.
Source: erdosproblems.com/545 | Last verified: January 15, 2026