##
**Zentralblatt MATH**

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

**Zbl.No: ** 209.28001

**Autor: ** Erdös, Paul; Simonovits, M.

**Title: ** Some extremal problems in graph theory (In English)

**Source: ** Combinat. Theory Appl., Colloquia Math. Soc. Janos Bolyai 4, 377-390 (1970).

**Review: ** [For the entire collection see Zbl 205.00201.]

The authors prove several results on extremal graphs and state several unsolved problems. Here we only state one theorem. Let C be the graph of 8 vertices and 12 edges determined by the vertices and edges of a cube. The authors prove that every graph of n vertices and c_{1}n^{8/5} edges contains C as a subgraph. It is an unsolved problem if this theorem is best possible. In other words we do not know if there is a graph of n vertices and c_{2}n^{8/5} edges which does not contain C as a subgraph.

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

**Citations: ** Zbl 205.00201(EA)

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag