Erdős Problem #614
No proof or disproof is known, and it isn't known whether a finite computation could settle it.
What the community database records, not our verdict. erdosproblems.com no longer shows statuses (why).
Attempts
submit one →Read our full write-up →
f(n,k) is the fewest edges forcing every (k+2)-set of vertices to induce a subgraph with a vertex of degree ≥k. Round 1 reduced it to a finite-family Turán problem and flagged the general formula as unproven. Round 2 pushed on that gap — and mostly settled it, except for one claim we caught overreaching: it silently treated the 50-year-open Erdős–Simonovits even-cycle conjecture as solved. Corrected, and the corrected version is the more interesting finding: for most k, a clean formula is provably at least as hard as that named open problem — that's WHY it doesn't exist, not just that nobody's found it yet. Round 3 maps the regime Round 2 left untouched — the near-diagonal one (n−k small): the actual 1996 Erdős–Reid–Schelp–Staton theorem and Pikhurko–Thomason's 2002 follow-up, which disproves the ERSS conjecture, gives the k→∞ asymptotic, and proves the naive split-graph fails off-diagonal — plus an unconditional f(n,k)=C(n,2)−o(n²) for every fixed k. The fixed-k orders Round 2 already proved (k=2,3,…) re-derive here; they're confirmation, not new ground.
LIVE