Smaller Subgraphs of Minimum Degree $k$

[摘要] In 1990 Erdős, Faudree, Rousseau and Schelp proved that for $k \ge 2$, every graph with $n \ge k+1$ vertices and $(k-1)(n-k+2)+\binom{k-2}{2}+1$ edges contains a subgraph of minimum degree $k$ on at most $n-\sqrt{n/6k^3}$ vertices. They conjectured that i

[学科分类] 离散数学和组合数学

[关键词] Graph theory;Minimum degree