On the Structure of Edge Graphs

Every graph appearing in this note is a finite edge graph without loops and multiple edges. Denote by G(n, m) a graph with n vertices and ni edges . K r (t) denotes a graph with r groups of t vertices each, in which two vertices are connected if and only if they belong to different groups . By dividing n vertices into r-1 almost equal groups and connecting the points in different groups one obtains a graph on n vertices with ((r 2)/2(r 1) + u (1)) 11 2 edges which does not contain a Kr(l) . On the other hand, it was shown by Erdős and Stone [7] that ((r 2)/2(r 1) + s) n2 (e > 0) edges assure already the existence of a Kr(t), where t -~ oo as n -p co . This result is the inost essential part of the theorems on the structure of extremal graphs, see e .g. [3], [4], [6], [9] . Let us formulate the result of Erdős and Stone more precisely . Given n, r and e, put rn = [((r-2)/2(r-1)+e)n2] ([x] denotes the integer part of x) and define g(n, r, e) = min {t : every G(n, in) contains a K r (t)} .