##
**Zentralblatt MATH**

**Publications of (and about) Paul Erdös**

**Zbl.No: ** 865.05052

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Jagota, Arun; Luczak, Tomasz

**Title: ** Large subgraphs of minimal density or degree. (In English)

**Source: ** J. Comb. Math. Comb. Comput. 22, 87-96 (1996).

**Review: ** Authors' abstract: This paper addresses the following questions. In any graph G with at least \alpha\binom{n}{2} edges, how large of an induced subgraph H can we guarantee the existence of with minimum degree \delta(H) \geq \lfloor\alpha|V(H)|\rfloor? In any graph G with at least \alpha\binom{n}{2}-f(n) edges, where f(n) is an increasing function of n, how large of an induced subgraph H can we guarantee the existence of containing at least \alpha\binom{|V(H)|}{2} edges? In any graph G with at least \alpha n^{2} edges, how large of an induced subgraph H can we guarantee the existence of with at least \alpha|V(H)|^{2}+\Omega(n) edges? For \alpha = 1- ^{1}/_{r} for r = 2,3,..., the answer is zero since if G is a complete r-partite graph, no subgraph H of G has more than \alpha|V(H)|^{2} edges. However, we show that for all admissible \alpha except these, the answer is \Omega(n). In any graph G with minimum degree \delta(G) \geq \alpha n-f(n), where f(n) = o(n), how large of an induced subgraph H can we guarantee the existence of with minimum degree \delta(H) \geq \alpha|V(H)|?

**Reviewer: ** B.Andrásfai (Budapest)

**Classif.: ** * 05C35 Extremal problems (graph theory)

**Keywords: ** induced subgraph; minimum degree

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag