##
**Zentralblatt MATH**

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

**Zbl.No: ** 116.01202

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

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

**Source: ** Publ. Math. Inst. Hung. Acad. Sci., Ser. A 7, 459-464 (1962).

**Review: ** Let G and \bar G (the "complement" of G) be graphs with the same vertices and without loops or multiple edges, such that every two distinct vertices are joined by an edge in exactly one of these graphs. C_{k} (G) is the number of complete subgraphs of G with k vertices. Theorem 1 states that for every k \geq 3 and every n, there exists a G with n vertices such that C_{k} (G)+C_{k} (\bar G) < {n \choose k} 2^{1-{k \choose 2}}. Theorem 2 and 3 determine the maximum value of C_{k} (G) as G runs over (in the case of Theorem 2) all graphs with l edges and (in Theorem 3) all graphs with n vertices which do not posses a complete subgraph with l vertices. Some unsolved related problems are mentioned.

**Reviewer: ** C.St.J.A.Nash-Williams

**Classif.: ** * 05C30 Enumeration of graphs and maps

**Index Words: ** combinatorics

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag