##
**Zentralblatt MATH**

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

**Zbl.No: ** 131.21001

**Autor: ** Erdös, Pál; Rényi, Alfréd

**Title: ** On a problem in the theory of graphs (In Hungarian)

**Source: ** Publ. Math. Inst. Hung. Acad. Sci., Ser. B 7, 623-639 (1963).

**Review: ** Let H_{2}(n,k) denote the set of all (non-directed) graphs G_{n} having n prescribed vertices, in which the maximum of the valencies of the vertices is equal to k, and the diameter of which is \leq 2. We put F_{2} (n,k) = **max** N (G_{n}), G_{n} in H_{2}(n,k) where N(G) denotes the number of edges of the graph G. [If H_{2}(n,k) is empty we put F_{2}(n,k) = +oo.] The following inequalities are proved: Theorem 1. F_{2}(n,k) \geq n(n-1)/2k. Theorem 2. F_{2}(n,k) \geq n(n-1)/(k+8n/k) if k^{2} > 8n. It is shown further by effective construction that Theorem 1 is asymptotically best possible, and that Theorem 2 is also asymptotically best possible in the case k^{2}/n ––> +oo. The constructions are based on the use of finite geometries.

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

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag