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
View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
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-04-11
