← All problems

Erdős–Faudree–Rousseau–Schelp small-subgraph problem

For every integer k≥2k\ge 2, there exists a constant εk>0\varepsilon_k>0 such that, for every sufficiently large integer nn, every graph GG on nn vertices satisfying e(G)>(k−1)n−(k2)e(G)>(k-1)n-\binom{k}{2} contains a subgraph on at most (1−εk)n(1-\varepsilon_k)n vertices whose minimum degree is at least kk.

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

The original conjecture has a claimed proof, while a new unrefereed preprint gives stronger quantitative results for related cases.

The Erdős–Faudree–Rousseau–Schelp conjecture asks whether one extra edge beyond the extremal threshold forces a subgraph of minimum degree at least kk after deleting a fixed positive proportion of the vertices. A preprint by Sauermann claims a complete proof; the latest work extends the quantitative picture beyond that statement.

Known results

  • Erdős, Faudree, Rousseau, and Schelp (1990): deletion of at least n/6k3\sqrt{n}/\sqrt{6k^3} vertices.
  • A 2017 paper improved this to deletion of Ω(n/log⁡n)\Omega(n/\log n) vertices.
  • Sauermann’s preprint, submitted in 2017 and revised in 2018, claims deletion of at least εkn\varepsilon_k n vertices for some εk>0\varepsilon_k>0.

October 2026 quantitative extension

Hunter, Barnabás Janzer, Oliver Janzer, and Benny Sudakov report that, for even ss, the relevant bound is Os ⁣(max⁡{n/ds/(s−2)(log⁡n)180,log⁡n})O_s\!\left(\max\left\{n/d^{s/(s-2)}(\log n)^{180},\log n\right\}\right), alongside a tight-exponent forbidden-family result for all positive ss. This is claimed progress, not a refereed verification.

Current status (as of October 2026): The original conjecture has a claimed but unverified proof, and the newer quantitative extensions remain unrefereed; the broader formulation is not independently settled.

Sources

Solutions 0

No solutions have been posted yet.