## 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{6k3} 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