ON THE MAXIMAL NUMBER OF EDGES IN A GRAPH - Khadzhiivanov, Nikolay (Ann. Sofia Univ. Fac. Math. and Inf., 1991)
Let K(h_1,h_2,..,h_s) be the complete s-partite graph with h_i vertices in i-th class. For n geq s ≥ r we denote by T_s(n;h_1,h_2,..,h_r) the n-graph K(h_1,h_2,..h_s) with |h_i-h_j| ≤ 1 for each pair i,j:r <i <j ≤ s. When r=0 this is the Turan’s graph T_s(n). The number of edges of a graph G is denoted by e(G). Main theorem. Let n,s,α_1,α_2, ..,α_r(r geq 0) be natural numbers and n ≥ s ≥ r, α_1+α_2+..+α_r ≤ n, 0.2cm α_i ≥ [ns], 0.2cm i =1,2,..,r. Let G be an n-graph without K_s+1, having disjoint family of independent vertex sets A_1, A_2,..,A_r, 0.2cm |A_i|≥ α_i, i=1,2,..,r. Then e(G) ≤ e (T_s(n;α_1,α_2,..,α_r)) and the equality holds iff G=T_s(n;α_1,α_2,..,α_r) and |A_i|=α_i; i=1,2,..,r For r=0 this is equivalent to the Turans theorem [3]. For r=1 it was stated together with V. Nikiforov more than 10 years ago. Corollary. Let n, s, α_1, α_2,..,α_r(r geq 1) be natural numbers, n ≥ s ≥ r, 0.2cm α_1+α_2+..+α_r≤ n, 0.2cm α_i geq [ns], i=1,2,..,r. Let G be an nvertex graph without K_s+1 and having disjoint family of vertex sets A_1,A_2,...,A_r with the following properties: 1) |A_i|≥ α_i and 2) in A_i there is a vertex α_i such that each of the vertices in A_i has at most the degree of α_i and is non-adjacent to α_i. Then e(G)≤ e(T_s(n;α_1,α_2,..,α_r)) and the equality holds iff G=T_s(n;α_1,α_2,..,α_r) and the sets A_i are its chromatic classes. The assumption α_i ≥ [ns] is essential in the above two propositions. So, for r=1 it is not true that if α_1 < [ns] then the graph T_s(n,α_1) has maximal number of edges among the n-graph without K_s+1 and having an independant set A_1 with at least α_1 vertices. Only the Turans graph T_s(n) has maximal number of edges in this class of graphs.