##
**Zentralblatt MATH**

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

**Zbl.No: ** 177.52502

**Autor: ** Erdös, Pál

**Title: ** On the number of complete subgraphs and circuits contained in graphs (In English)

**Source: ** Cas. Pestováni Mat. 94, 290-296 (1969).

**Review: ** Let G(n; k) be a graph of n vertices and k edges. K_{p} denotes a complete graph of p vertices. Let n \equiv r (mod p-1), m(n; p = {p-2 \over 2(p-1)} (n^{2}-r^{2})+{r \choose 2}, 0 \leq r \leq p-1. A well known theorem of Turán states that every G(n; m(n; p)+1) contains a K_{p} and that this result is best possible. Denote by f_{n}(p; 1) the largest integer so that every G(n; m(n; p)+1) contains at least f_{n}(p; 1) K_{p}'s. The author proves that for n > n_{0}(p) f_{n}(p; 1) = **prod**_{i = 0}^{p-1} **[**{n+1 \over p-1}**]**. In particular f_{3n}(4,1) = n^{2}. Several further results are proved, f_{n}(p,1) is determined for 1 < \epsilon_{p}n and several unsolved problems are stated. [See also P. Erdös, Illinois J. Math. 6, 122-127 (1962; Zbl 099.39401)]

**Classif.: ** * 05C20 Directed graphs (digraphs)

05C38 Paths and cycles

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag