##
**Zentralblatt MATH**

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

**Zbl.No: ** 105.17504

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

**Title: ** Über ein Extremalproblem in der Graphentheorie. (On an extremal problem in graph theory.) (In German)

**Source: ** Arch. Math. 13, Festschrift Reinhold Baer 222-227 (1962).

**Review: ** The author considers graphs without loops or multiple edges. He proves that, if n \geq 400 k^{2}, every graph with n vertices and at least l = [ ^{1}/_{4} (n-k+1)^{2}]+(k-1) (n- ^{1}/_{2} k+1) edges contains k disjoint triangles, with the exception of an (up to isomorphism) unique graph with n vertices and l edges. He states that a more complicated version of the proof can replace 400 k^{2} by Ck, where C is an absolute constant. The following further theorems are stated with brief hints for proof. Let G be a graph with n vertices. (1) If k \equiv n (mod 2) and every vertex has valency \geq ^{1}/_{2} (n+k) and n \geq some n_{0}(k), then G contains k disjoint triangles. (2) If n > ck, where c is a sufficiently large absolute constant, and G has ^{1}/_{4} n^{2}+k edges, then G contains k triangles no two of which have a common edge.

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

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

**Index Words: ** topology

© European Mathematical Society & FIZ Karlsruhe & Springer-Verlag