##
**Zentralblatt MATH**

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

**Zbl.No: ** 518.05044

**Autor: ** Erdös, Paul; Sos, V.T.

**Title: ** On a generalization of Turan's graph-theorem. (In English)

**Source: ** Studies in pure mathematics, Mem. of P. Turan, 181-185 (1983).

**Review: ** [This article was published in the book announced in Zbl 512.00007.]

Let t(n,k) be the number of edges in Turán's graph, i.e. the complete (k-1)-partite graph on n vertices with color classes of nearly equal sizes. The following refinement of Turán's theorem is proved: if the graph G on n vertices has more than t(n,k) edges, then there is a vertex v such that e(v) > t(d(v),k-1), where d(v) is the degree of v and e(v) is the number of edges in the graph induced by the neighbors of v. This result was proved independently by *B.Bollobás* and *A.Thomason* [Comb. Theory, Ser. B 31, 111-114 (1981; Zbl 456.05037)]; and a very short proof was published by *J.A.Bondy* [ibid., Ser. B 34, 109-111 (1983; Zbl 498.05041)].

**Reviewer: ** D.de Caen

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

**Keywords: ** complete subgraphs; Turan's theorem

**Citations: ** Zbl.512.00007; Zbl.456.05037; Zbl.498.05041

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag