Let $G$ be a graph with $n$ vertices and $m$ edges, and let $d=\lfloor\frac{m}{n}\rfloor$ be the rounded-down average-degree. A lemma that is attributed to Erdos says that $G$ has a non-empty induced sub-graph $H$ of minimum degree at least $d$ (in particular, the lemma is attributed to [1], but I could not find it there).


However, the lemma does not give a bound on the size of $H$. I am looking for a lemma of the following form: There exists an induced sub-graph $H$ that has minimal degree at least $d/100$, and contains a constant fraction of the edges of $G$ (the fraction $\frac{1}{100}$ can be replaced by any constant $\varepsilon$).


Is such a lemma known?


[1] P. Erdos (1963),"On the structure of linear graphs", Israel Journal of Mathematics 1, 156-160.



Dense high-degree sub-graphs of dense graphs
Assuming you mean "at least a constant fraction of the edges", this is true and the proof is forced upon on us in the same way as for the original lemma. I'll change notation to have $d$ as the target minimum degree.


If we have a graph $G$ and want a subgraph of minimum degree at least $d$, then we have no choice but to delete any vertices of degree less than $d$, then any vertices of degree less than $d$ in the remainder, and so on. These vertex deletions result in a total number of edge deletions that is less than $nd$, so we have some graph $H$ left provided $nd \leq e(G)$, and any such $H$ will have minimum degree at least $d$. This is the usual proof. We now further observe that $e(H) > e(G) - nd$, so if $e(G)$ is large compared to $nd$ then only a small fraction of the edges of $G$ were deleted to obtain $H$.


