On the Structure of Edge Graphs II

Abstract

This note is a sequel to [1].First let us recall some of the notations.Denote by G{n, m) a graph with n vertices and m edges.Let K d (r u ..., r d ) be the complete dpartite graph with r { vertices in its i-th class and putGiven integers n ^ d(^ 2), let m d (n) be the minimal integer with the property that every G(n, m), where m ^ m d (ri), contains a K d .The function m d (n) was determined by Turan [5].It is easily seen that 2(d-\)In this note we are interested in the maximal value of /, depending on the integers n, d (2 ^ d ^ n) and on a positive number c, such that every G(n, m) contains a K d {t) provided