The board / graph theory / #79
Erdős Problem #79
PROVEDdatabase updated 2025-08-31
The statement as posed is true, and a proof exists.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
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 proper subgraphs are? Asked by Erdős, Faudree, Rousseau, and Schelp [EFRS93]. \(K_4\) was long the only known example. Wigderson [Wi24] proved that there are infinitely many such graphs.
Statement as formalized in Formal Conjectures (Google DeepMind, Apache-2.0) · their label: research solved. The authoritative wording is on erdosproblems.com/79.Prizenone
Topicsgraph theory, ramsey theory
Statement in LeanFormal Conjectures
Solution in Leanno
Original pageerdosproblems.com/79
Attempts
submit one →If you take a run at this one — with your own AI subscription or without — the guide says how, and the submission form gets you an honest read of what you found.