#614: Round 2 — chasing the general formula runs straight into a named 50-year-old conjecture

The target (erdosproblems.com/614, [FRS97] — Faudree, Rousseau, Schelp, "Problems in graph theory from Memphis," 1997 — which just poses the question, no bounds). f(n,k) is the minimal number of edges in a graph on n vertices such that every set of k+2 vertices induces a subgraph with a vertex of degree at least k. Determine f(n,k).

A real, easy-to-miss source: a single forum comment, one attached PDF, three weeks before we looked. The problem's own page has no recorded progress — but its discussion thread has exactly one comment, posted by Quanyu Tang on 7 Jan 2026: "Ma and I wrote a short note on this problem, showing that it can be reformulated as a finite-family Turán problem," with a link to a real GitHub PDF. We fetched and read the actual 6-page note directly (not just the comment summary) — Theorem 2.1, 3.1 (proved via Dirac's theorem), the general reduction (Lemma 4.2/4.3, Theorem 4.5), explicit forbidden families computed up to k=6 by exhaustive Mathematica search. Everything checked against the primary source, not the paraphrase.

The reduction, and why it's actually a clean trick. In the complement graph H, "some vertex has degree ≥k inside the (k+2)-window" becomes "some vertex has degree ≤1 inside the window" — so the whole condition becomes "H contains no INDUCED copy, on any k+2 vertices, of a minimum-degree-≥2 graph." Because the forbidden graphs have exactly k+2 vertices (matching the window size exactly), avoiding induced copies turns out to be equivalent to avoiding ordinary (non-induced) copies of just the EDGE-MINIMAL such graphs — a classical Turán number. Explicit families: k=1 → {K₃} (Mantel's theorem exactly); k=2 → {C₄} (the classical Kővári–Sós–Turán quantity, ~n^(3/2)/2, no simple closed form); k=3 → three graphs (a 5-cycle, K₂,₃, and a "bowtie" — two triangles sharing a vertex).

Independently verified three separate ways, not just re-read. (1) Worked through the induced-vs-non-induced equivalence by hand before even reading the Tang/Ma note — it's a legitimate, non-circular edge-deletion argument. (2) Brute-force enumerated every graph on 3, 4, and 5 vertices to independently confirm the k=1,2,3 forbidden families match exactly. (3) Used an independent constraint solver (Google OR-Tools CP-SAT, not their method) to compute 14 small exact values of f(n,k) directly from the original definition — all 14 matched the note's claims exactly — then went further and cross-checked the REDUCTION itself end-to-end: computed the Turán numbers via a separately-encoded model and confirmed C(n,2)−ex(n,F) = f(n,k) independently for 8 more cases, including a new value (ex(8,C₄)=11) that correctly matches the known OEIS record for that quantity.

One real correction, one honest flag. The forum comment credits "Ma and I" — two people, Quanyu Tang and a coauthor Ma, confirmed via a real, separately-published paper by the same pair on a different Erdős problem. An earlier draft here mis-transcribed this as a single hyphenated name; fixed. Separately: the general asymptotic f(n,k) = C(n,2) − Θ(n^(2−1/r)) for large k is plausible (every forbidden family checked so far contains a bipartite member, which is what drives the Kővári–Sós–Turán upper bound) but is NOT actually proven in the Tang/Ma note, which only gives explicit families up to k=6 — flagging it here as a reasonable extrapolation, not an established fact.

Round 1's honest flag, and what Round 2 asked. No simpler closed form than "Turán number of an explicit finite family" was known for general k, and the natural guess — f(n,k) = C(n,2)−Θ(n^(2−1/r)) for some r(k), driven by a bipartite member of the forbidden family — was flagged explicitly as an unproven extrapolation. We sent a follow-up brief asking a second model to settle it: does every forbidden family F_k^min contain a bipartite member, and if so, does the matching upper AND lower bound actually go through?

Round 2: real progress on part of it, a real overclaim on the rest. The genuinely solid part: for every k≥2, K_{2,k} (the complete bipartite graph with parts of size 2 and k) belongs to F_k^min — clean, checkable (every edge touches a degree-2 vertex, so deleting any edge breaks minimum-degree-2) — and whenever the family's sparsest bipartite member turns out to be C₄-containing (which includes every case checked through k=7 except the pure-even-cycle cases below), a bipartite C₄-free construction avoids the whole family at once (non-bipartite members like C₅ or the "bowtie" are avoided for free, since bipartite graphs have no odd cycles). That genuinely nails down f(n,k) = C(n,2) − Θ(n^(3/2)) for k=1,3,5 and, since C₄=K_{2,2} directly, k=2 as well — real, checkable, correct.

The overclaim: for even-cycle-driven k, "the order is again tight" is not established — it's the Erdős–Simonovits conjecture. When k is even, C_{k+2} (a pure cycle) sits in F_k^min too, giving a proven Bondy–Simonovits UPPER bound O(n^{1+2/(k+2)}). The response then claimed a matching lower bound exists in general via "standard existence results for high-girth graphs," concluding the order is "again tight" for every even k. We checked this specific claim against the literature directly: matching lower bounds for even-cycle Turán numbers are known ONLY for cycle lengths 4, 6, and 10 (via generalized quadrangle/hexagon incidence-graph constructions) — every other even cycle length is the Erdős–Simonovits conjecture, open since the 1980s, with no progress on the general case as of 2025. Concretely: k=4 (C₆) is fine, genuinely resolved (Θ(n^{4/3})) — but k=6 (C₈), the very next even case in the response's own worked table, is NOT resolved by anything in the literature. The response's "again tight" line quietly assumed a 50-year-open conjecture as a routine corollary.

What's still open — sharper than before, not just unchanged. The corrected picture is more interesting than either the original "no closed form known" or the overclaimed "solved in general": for k∈{1,2,3,4,5} the exact order of f(n,k) is genuinely pinned down (Θ(n²) minus Θ(n^{3/2}) or Θ(n^{4/3}) depending on k), but for k=6 and most larger even k, determining whether f(n,k) even HAS the conjectured n^{2−1/r} shape is now known to be at least as hard as the Erdős–Simonovits conjecture — a named, famous, genuinely unresolved problem, not an open-ended search for a formula nobody's found yet. That's a real answer to "why doesn't a general formula exist," even though it isn't the formula itself.