##
**Zentralblatt MATH**

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

**Zbl.No: ** 714.05033

**Autor: ** Erdös, Paul; Faudree, Ralph J.; Rousseau, C.C.; Schelp, R.H.

**Title: ** Subgraphs of minimal degree k. (In English)

**Source: ** Discrete Math. 85, No.1, 53-58 (1990).

**Review: ** For k \geq 2, any graph G with n vertices and (k-1)(n-k+2)+\binom{k- 2}{2} edges has a subgraph of minimum degree at least k; however, this subgraph need not be proper. It is shown that if G has at least (k-1)(n- k+2)+\binom{k-2}{2}+1 edges, then there is a subgraph H of minimal degree k that has at most n-\sqrt{n}/\sqrt{6k^{3}} vertices. Also, conditions that insurethe existence of smaller subgraphs of minimum degree k are given.

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

**Keywords: ** subgraph of minimum degree

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag