Status
On this page
Status
Topics
Status
On this page
Status
Topics
Let be such that any subgraph on vertices has at most edges. Is it true that, if has edges and no isolated vertices, then
Let be such that any subgraph on vertices has at most edges. Is it true that, if has edges and no isolated vertices, then
Source: erdosproblems.com/566
No claim settles this problem.
The site labels the problem OPEN, and the corrected Statement is open: no proof or disproof was found in the search whose scope the Current assessment records. Partial results are known, from two refereed papers recorded as accepted partial claims: [EFRS93] for connected graphs with at most one more edge than vertices (Theorem 4), the graphs with exactly edges (Corollary 2) and the graphs with Turán number (Theorem 5), on its claim page (Erdős, Faudree, Rousseau and Schelp, 1993); and [BGS24] for the subdivisions of on at least six vertices (Theorem 4), on its claim page (Bradač, Gishboliner and Sudakov, 2022). A September 2026 preprint claims every graph without a minor, including all -trees, which meet the hypothesis with equality; it is a partial claim recorded, unreviewed, on its claim page (Barría, 2026). The minimal undecided instances named in 1993, , and (Question 2, the site's Problem 567), remain undecided in the sources found. No full claim exists, so the problem is open with no claim. This is a bounded negative finding, not a certificate of openness.
The site's wording fails at the smallest subgraph sizes. Its hypothesis quantifies over every subgraph on vertices, including , and a single vertex has edges, so no graph with a vertex satisfies it (the vertexless graph, if admitted, fails at , where ); the question then concerns an empty class of graphs and holds only for want of an instance. The failure is this page's own elementary check. The defect is already in the posers' text: [EFRS93] Question 1 (p. 398) asks "If every subgraph of satisfies , is necessarily Ramsey size linear?", and its prose form on p. 395 ("each subgraph of order has size at most ") is unrestricted as well. The change inserts "" after "any subgraph on ", which excludes exactly the sizes at which no graph can meet the hypothesis; it is an exclusion of size-degenerate values, the formal-conjectures file states the same restriction to vertex sets of at least two elements (it follows the site and is not a further source), and no source of higher rank supplies a range. Above the excluded sizes no failure remains: for and the bound ( and edges) holds in every graph, and at it excludes exactly , which is not Ramsey size linear by [EFRS93] Corollary 1 (, ). No result about the site's wording exists beyond the vacuity check recorded here, which settles no instance of the corrected Statement.