Smaller subgraphs of minimum degree \(k\) (Q2409841)

Summary: In [Discrete Math. 85, No. 1, 53--58 (1990; Zbl 0714.05033)], \textit{P. Erdős} et al. proved that for \(k \geq 2\), every graph with \(n \geq 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 it is possible to remove at least \(\varepsilon_k n\) many vertices and remain with a subgraph of minimum degree \(k\), for some \(\varepsilon_k0\). We make progress towards their conjecture by showing that one can remove at least order of \(\Omega(n/\log n)\) many vertices.