How many edges force an nn-vertex graph to contain a subgraph of minimum degree at least kk that is genuinely smaller than the whole graph, and how small can such a subgraph be guaranteed to be? Erdős, Faudree, Rousseau and Schelp (1990) determined the exact threshold tk(n)t_k(n) above which a proper subgraph of minimum degree kk is forced, and conjectured — a question originating with Erdős — that a single edge above the threshold already forces such a subgraph on at most (1−η(k))n(1-\eta(k))n vertices for some constant η(k)>0\eta(k)>0; Sauermann (2019) proved this with η(k)=Ω(k−3)\eta(k)=\Omega(k^{-3}). The surviving open core, posed in their 1991 companion paper, is the full density–size tradeoff: determine, exactly or up to constant factors, the function c(k,ε)c(k,\varepsilon) — the least edge density forcing a subgraph of minimum degree at least kk on at most εn\varepsilon n vertices — equivalently the minimum-degree analogue u(n,d,k)u(n,d,k) of the average-degree small-subgraph function that Janzer, Sudakov and Tomon (2024) determined up to polylogarithmic factors while stating that the minimum-degree variant is 'completely open for every s≥3s\ge 3'. For fixed k≥3k\ge 3 the known bounds on c(k,ε)c(k,\varepsilon) differ by a polynomial factor ε−1/k\varepsilon^{-1/k}, and the correct order of η(k)\eta(k) itself is undetermined.

Background

All graphs are finite and simple. The minimum degree δ(H)\delta(H) of a graph HH is the smallest number of neighbours of a vertex of HH; a subgraph is proper if it has fewer vertices than its host graph. Erdős, Faudree, Rousseau and Schelp studied the forcing question: how many edges guarantee that an nn-vertex graph contains a subgraph of minimum degree at least kk, and — harder — a proper such subgraph? They determined the exact threshold tk(n)=(k−1)(n−k+2)+(k−22)t_k(n)=(k-1)(n-k+2)+\binom{k-2}{2} (tk(n)t_k(n) edges always force some subgraph of minimum degree at least kk, possibly the whole graph; tk(n)+1t_k(n)+1 edges always force a proper one). The extremal example is the generalized wheel W(k−2,n)=Kk−2+Cn−k+2W(k-2,n)=K_{k-2}+C_{n-k+2}, the graph join of a clique on k−2k-2 vertices and a cycle on n−k+2n-k+2 vertices (every clique vertex adjacent to every cycle vertex); it has exactly tk(n)t_k(n) edges, minimum degree exactly kk, and no proper subgraph of minimum degree kk at all.

Since the host graph itself may be the only witness, the quantitative question is how much smaller than nn a forced subgraph can be. Erdős, Faudree, Rousseau and Schelp proved that tk(n)+1t_k(n)+1 edges force a subgraph of minimum degree at least kk on at most n−⌊n/(6k3)⌋n-\lfloor\sqrt{n/(6k^3)}\rfloor vertices, and conjectured that one edge above the threshold already forces a linear saving: there is a constant η(k)>0\eta(k)>0 such that every graph on n≥k+1n\ge k+1 vertices with tk(n)+1t_k(n)+1 edges contains a subgraph HH with δ(H)≥k\delta(H)\ge k and ∣H∣≤(1−η(k))n|H|\le(1-\eta(k))n. The conjecture originated with Erdős for k=3k=3 and also appears in his 1993 list of favourite problems. Mousset, Noever and Škorić (2017) improved the guaranteed saving to n−n/(8(k+1)5log⁡2n)n-n/(8(k+1)^5\log_2 n), where log⁡2\log_2 denotes the base-2 logarithm (the published Electronic Journal of Combinatorics version; the arXiv preprint states the constant 44 in place of 88), and Sauermann (2019) proved the conjecture with an explicit constant: at the threshold edge count one may take ηk≥1/(104k3)\eta_k\ge 1/(10^4k^3), i.e. η(k)=Ω(k−3)\eta(k)=\Omega(k^{-3}). Sauermann makes no optimality claim for these constants; the generalized wheel itself, with one chord added to split its cycle into arcs of length about (n−k+2)/2(n-k+2)/2, keeps tk(n)+1t_k(n)+1 edges while forcing every subgraph of minimum degree at least kk to span at least n/2n/2 vertices, giving η(k)≤1/2+o(1)\eta(k)\le 1/2+o(1). The order of magnitude of η(k)\eta(k), known to lie between Ω(k−3)\Omega(k^{-3}) and 1/2+o(1)1/2+o(1), therefore remains open.

The 1991 companion paper of the same authors poses the general density version: for fixed kk and 0<ε<10<\varepsilon<1, determine the smallest constant c(k,ε)c(k,\varepsilon) such that every sufficiently large nn-vertex graph with at least c(k,ε)⋅nc(k,\varepsilon)\cdot n edges contains a subgraph of minimum degree at least kk on at most εn\varepsilon n vertices. (The 'sufficiently large nn' reading is forced: for nn below about k/εk/\varepsilon no subgraph on εn\varepsilon n vertices can have minimum degree kk.) Two constructions frame the problem. The generalized wheel shows c(k,ε)≥k−1c(k,\varepsilon)\ge k-1 for every fixed ε<1\varepsilon<1. The (k−1)(k-1)-th power of a cycle, Cnk−1C_n^{k-1} — the graph on nn cyclically ordered vertices in which vertices at cyclic distance at most k−1k-1 are adjacent — has (k−1)n(k-1)n edges (degree 2(k−1)2(k-1) at every vertex), and every subgraph of minimum degree at least kk in it spans a positive fraction of the nn vertices, so c(k,ε)>k−1c(k,\varepsilon)>k-1 for all sufficiently small ε\varepsilon. By monotonicity in ε\varepsilon and Sauermann's theorem, the curve is in fact pinned to c(k,ε)=k−1c(k,\varepsilon)=k-1 throughout ε∈[1−η0(k),1)\varepsilon\in[1-\eta_0(k),1) for some η0(k)=Ω(k−3)\eta_0(k)=\Omega(k^{-3}).

The companion question with average degree in place of minimum degree was recently settled up to a polylogarithmic factor by Janzer, Sudakov and Tomon (2024), resolving a 2016 conjecture on generalized girth problems: every nn-vertex graph of average degree at least dd, where d≤n(s−2)/sd\le n^{(s-2)/s}, contains a subgraph of average degree at least ss on at most n d−s/(s−2)(log⁡d)Cn\,d^{-s/(s-2)}(\log d)^C vertices, matching the random-graph lower bound up to the polylogarithmic term. For the minimum-degree variant the same authors write that it 'is completely open for every s≥3s\ge 3, and our methods do not seem to be adaptable for this problem'. What is known for minimum degree: every nn-vertex graph of average degree at least dd, where d≥2sd\ge 2s and d≤n(s−1)/sd\le n^{(s-1)/s}, contains a subgraph of minimum degree at least ss on at most n d−s/(s−1)(log⁡d)Cn\,d^{-s/(s-1)}(\log d)^C vertices (their Corollary 1.5, using that average degree at least 2s2s forces a subgraph of minimum degree at least ss), while their probabilistic construction gives graphs of average degree at least dd in which every subgraph of average degree at least ss — hence every subgraph of minimum degree at least ss — has at least cs n d−s/(s−2)c_s\,n\,d^{-s/(s-2)} vertices. For fixed k≥3k\ge 3 and small ε\varepsilon, setting d=Θ(c)d=\Theta(c) in these two bounds yields Ωk(ε−(k−2)/k)≤c(k,ε)≤Ok(ε−(k−1)/kpolylog⁡(1/ε)),\Omega_k\big(\varepsilon^{-(k-2)/k}\big)\le c(k,\varepsilon)\le O_k\big(\varepsilon^{-(k-1)/k}\operatorname{polylog}(1/\varepsilon)\big), an exponent gap of a factor ε−1/k\varepsilon^{-1/k}. In the much denser regime d≥n1−2/s+ε′d\ge n^{1-2/s+\varepsilon'}, the minimum-degree version is known for s=3s=3 (via a recent Turán-type result of Janzer on graphs with minimum degree 3 — Turán-type meaning an extremal problem on the maximum number of edges in a graph avoiding a given subgraph — which even yields regular subgraphs) and for even ss (via results quoted by Janzer–Sudakov–Tomon), and open for odd s>3s>3 — a different density window from the c(k,ε)c(k,\varepsilon) regime but the same family of questions.

For k=2k=2 the question is classical girth theory — the girth of a graph is the length of its shortest cycle, and a smallest subgraph of minimum degree 2 is exactly a shortest cycle — and it is settled: c(2,ε)=1c(2,\varepsilon)=1 for every fixed ε<1\varepsilon<1, since a graph of girth greater than εn\varepsilon n has at most n+O(log⁡n)n+O(\log n) edges by the Moore bound (the standard lower bound on the order of a graph of given girth and minimum degree), while a forest on nn vertices with its n−1n-1 edges contains no cycle at all. The substantive range is therefore k≥3k\ge 3.

Problem Statement

Determine the density–size tradeoff for forced subgraphs of minimum degree at least kk; that is, for integers k≥3k\ge 3 and 0<ε<10<\varepsilon<1 (both fixed, n→∞n\to\infty), determine exactly, or up to constant factors, the threshold c(k,ε)=inf⁡{c: for all sufficiently large n, every n-vertex graph with at least cn edges contains a subgraph H with δ(H)≥k and ∣H∣≤εn}.c(k,\varepsilon)=\inf\big\{c:\ \text{for all sufficiently large }n,\ \text{every }n\text{-vertex graph with at least }cn\text{ edges contains a subgraph }H\text{ with }\delta(H)\ge k\text{ and }|H|\le\varepsilon n\big\}. Equivalently, up to the factor of 2 between edge density and average degree, determine the function u(n,d,k)u(n,d,k) — the least uu such that every nn-vertex graph of average degree at least dd contains a subgraph of minimum degree at least kk on at most uu vertices — over the range 2(k−1)≤d≤n(k−2)/k2(k-1)\le d\le n^{(k-2)/k} in which it is finite and in which the average-degree analogue is settled up to polylogarithmic factors (for average degree below 2(k−1)−o(1)2(k-1)-o(1), corresponding to fewer than tk(n)t_k(n) edges, no subgraph of minimum degree at least kk is forced at all); Janzer, Sudakov and Tomon state that this minimum-degree question is 'completely open for every s≥3s\ge 3'. The objective is the general determination up to constant factors, for all fixed k≥3k\ge 3 and all 0<ε<10<\varepsilon<1; the two benchmark cases below are self-contained sub-goals of it, each a significant partial result whose resolution does not by itself complete that general determination: (i) the correct order of magnitude of η(k)\eta(k), defined as the supremum of the constants η\eta such that, for all sufficiently large nn, every nn-vertex graph with tk(n)+1t_k(n)+1 edges — where tk(n)=(k−1)(n−k+2)+(k−22)t_k(n)=(k-1)(n-k+2)+\binom{k-2}{2} is the exact forcing threshold — contains a subgraph HH with δ(H)≥k\delta(H)\ge k and ∣H∣≤(1−η)n|H|\le(1-\eta)n (known: η(k)≥1/(104k3)\eta(k)\ge 1/(10^4k^3) from Sauermann and η(k)≤1/2+o(1)\eta(k)\le 1/2+o(1) from the wheel-plus-chord construction, so the open content is the polynomial gap between these two bounds); (ii) for any fixed k≥3k\ge 3, closing the gap between c(k,ε)≥Ωk(ε−(k−2)/k)c(k,\varepsilon)\ge\Omega_k(\varepsilon^{-(k-2)/k}) and c(k,ε)≤Ok(ε−(k−1)/kpolylog⁡(1/ε))c(k,\varepsilon)\le O_k(\varepsilon^{-(k-1)/k}\operatorname{polylog}(1/\varepsilon)) as ε→0\varepsilon\to 0. The curve is already pinned to c(k,ε)=k−1c(k,\varepsilon)=k-1 on ε∈[1−η0(k),1)\varepsilon\in[1-\eta_0(k),1) for some η0(k)=Ω(k−3)\eta_0(k)=\Omega(k^{-3}), so the open range is ε<1−η0(k)\varepsilon<1-\eta_0(k), most sharply ε→0\varepsilon\to 0.

References

  1. P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, Subgraphs of minimal degree k, Discrete Mathematics 85(1):53–58, 1990. DOI: 10.1016/0012-365X(90)90162-B. https://doi.org/10.1016/0012-365X(90)90162-B
  2. P. Erdős, R. J. Faudree, C. C. Rousseau, R. H. Schelp, Edge conditions for the existence of minimal degree subgraphs, in: Graph Theory, Combinatorics, and Applications, Vol. 1 (Proceedings of the Sixth Quadrennial International Conference on the Theory and Applications of Graphs), Wiley, New York, 1991, pp. 419–434. Zbl 0840.05033, ISBN 0-471-60917-X. https://zbmath.org/0840.05033
  3. P. Erdős, Some of my favorite solved and unsolved problems in graph theory, Quaestiones Mathematicae 16(3):333–350, 1993. DOI: 10.1080/16073606.1993.9631741. https://doi.org/10.1080/16073606.1993.9631741
  4. P. Erdős, R. J. Faudree, A. Jagota, T. Łuczak, Large subgraphs of minimal density or degree, Journal of Combinatorial Mathematics and Combinatorial Computing 22:87–96, 1996. Zbl 0865.05052. https://zbmath.org/0865.05052
  5. F. Mousset, A. Noever, N. Škorić, Smaller subgraphs of minimum degree k, The Electronic Journal of Combinatorics 24(4), Paper #P4.9, 2017. DOI: 10.37236/7167, arXiv:1703.00273. https://doi.org/10.37236/7167
  6. L. Sauermann, A proof of a conjecture of Erdős, Faudree, Rousseau and Schelp on subgraphs of minimum degree k, Journal of Combinatorial Theory, Series B 134:36–75, 2019. DOI: 10.1016/j.jctb.2018.05.002, arXiv:1705.09979. https://doi.org/10.1016/j.jctb.2018.05.002
  7. O. Janzer, B. Sudakov, I. Tomon, Small subgraphs with large average degree, Combinatorica 44:785–800, 2024. DOI: 10.1007/s00493-024-00091-6, arXiv:2207.02170. https://doi.org/10.1007/s00493-024-00091-6
  8. O. Janzer, Disproof of a conjecture of Erdős and Simonovits on the Turán number of graphs with minimum degree 3, International Mathematics Research Notices 2023(10):8478–8494, 2023. DOI: 10.1093/imrn/rnac076, arXiv:2109.06110. https://doi.org/10.1093/imrn/rnac076
  9. L. Narins, A. Pokrovskiy, T. Szabó, Graphs without proper subgraphs of minimum degree 3 and short cycles, Combinatorica 37:495–519, 2017. DOI: 10.1007/s00493-015-3310-9. https://doi.org/10.1007/s00493-015-3310-9
  10. F. Di Braccio, K. Katsamaktsis, J. Ma, A. Malekshahian, Z. Zhao, Leaf-to-leaf paths and cycles in degree-critical graphs, Combinatorica 46, 2026. DOI: 10.1007/s00493-026-00205-2, arXiv:2504.11656. https://doi.org/10.1007/s00493-026-00205-2