Logo
All Random Solved Random Open
OPEN
Show that if $G$ has $\binom{n}{2}$ edges then \[R(G) \leq R(n).\] More generally, if $G$ has $\binom{n}{2}+t$ edges with $t\leq n$ then \[R(G)\leq R(H)\] where $H$ is the graph formed by connected a new vertex to $t$ of the vertices of $K_n$.
In other words, are cliques extremal for Ramsey numbers. Asked by Erdős and Graham.

See also the entry in the graphs problem collection.