Small subgraphs of large minimum degree
Abstract
In 1991, Erdős, Faudree, Rousseau and Schelp asked to estimate the smallest u=u(n,d,s) such that every n-vertex graph with average degree at least d has a subgraph on at most u vertices with minimum degree at least s. We resolve this problem up to polylogarithmic factors for all even values of s. More precisely, we prove that every n-vertex graph with minimum degree d≥ s has a subgraph on Os(max{n/(ds/(s−2))(log n)180,log n}) vertices with minimum degree at least s, whenever s≥ 4 is even. This improves a result of Janzer, Sudakov and Tomon, who obtained a similar conclusion for subgraphs of average degree at least s. We also prove that for every positive integer s and every ε>0, there exists a finite family ℋ of graphs with minimum degree s such that ex(n,ℋ)=O(n2−2/s+ε). This is tight and is the first result of similar kind that applies to odd values of s greater than 3.
Related
- A Sublinear Minimum-Degree Condition for $2$-Connected Subgraphs of All Orders
- On the Minimum Possible Maximum Degree of Induced Subgraphs of Product Graphs
- Bounded chromatic number of graphs with small clique number and large minimum degree
- Large induced subgraphs with k vertices of maximum degree
- On the minimum number of triangles in balanced tripartite graphs with large minimum degree
BibTeX
@misc{hunter2026small,
title = {{Small subgraphs of large minimum degree}},
author = {Zach Hunter and Barnabás Janzer and Oliver Janzer and Benny Sudakov},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.26763},
eprint = {2610.26763},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.26763},
}
RIS
TY - UNPB
TI - Small subgraphs of large minimum degree
AU - Zach Hunter
AU - Barnabás Janzer
AU - Oliver Janzer
AU - Benny Sudakov
PY - 2026
DA - 2026/10/19
PB - arXiv
DO - 10.48550/arxiv.2610.26763
UR - https://arxiv.org/abs/2610.26763
AB - In 1991, Erdős, Faudree, Rousseau and Schelp asked to estimate the smallest u=u(n,d,s) such that every n-vertex graph with average degree at least d has a subgraph on at most u vertices with minimum degree at least s. We resolve this problem up to polylogarithmic factors for all even values of s. More precisely, we prove that every n-vertex graph with minimum degree d≥ s has a subgraph on O_s(max{n/(d^s/(s−2))(log n)^180,log n}) vertices with minimum degree at least s, whenever s≥ 4 is even. This improves a result of Janzer, Sudakov and Tomon, who obtained a similar conclusion for subgraphs of average degree at least s. We also prove that for every positive integer s and every ε>0, there exists a finite family ℋ of graphs with minimum degree s such that ex(n,ℋ)=O(n^2−2/s+ε). This is tight and is the first result of similar kind that applies to odd values of s greater than 3.
ER -