PROVED
This has been solved in the affirmative.
We say $G$ is Ramsey size linear if $R(G,H)\ll m$ for all graphs $H$ with $m$ edges and no isolated vertices.
Are there infinitely many graphs $G$ which are not Ramsey size linear but such that all of its subgraphs are?
Asked by Erdős, Faudree, Rousseau, and Schelp
[EFRS93]. $K_4$ is the only known example of such a graph.
Wigderson
[Wi24] has proved that there are infinitely many such graphs (although his proof is not explicit, and an explicit example of such a graph apart from $K_4$ is still unknown).
View the LaTeX source
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #79, https://www.erdosproblems.com/79, accessed 2026-01-16
