ON THE MAXIMAL NUMBER OF EDGES IN A GRAPH

Abstract

Let $K(h_1,h_2,..,h_s)$ be the complete $s$-partite graph with $h_i$ vertices in $i$-th class. For $ngeqs\ge 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|\le 1$ for each pair $i,j:r<i<j\le 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,{\alpha }_1,{\alpha }_2,,..,{\alpha }_r(rgeq0)$ be natural numbers and $n\ge s\ge r,{\alpha }_1+{\alpha }_2+..+{\alpha }_r\le n,{\alpha }_i\ge [\frac{n}{s}],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,|A_i|\ge {\alpha }_i,i=1,2,..,r$. Then $$e(G)\le e(T_s(n;{\alpha }_1,{\alpha }_2,..,{\alpha }_r))$$ and the equality holds iff $$G=T_s(n;{\alpha }_1,{\alpha }_2,..,{\alpha }_r)$$ and $$|A_i|={\alpha }_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,{\alpha }_1,{\alpha }_2,..,{\alpha }_r(rgeq1)$ be natural numbers, $n\ge s\ge r,{\alpha }_1+{\alpha }_2+..+{\alpha }_r\le n,{\alpha }_{i}geq[\frac{n}{s}],i=1,2,..,r$. Let $G$ be an $n$vertex 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|\ge {\alpha }_i$ and 2) in $A_i$ there is a vertex ${\alpha }_i$ such that each of the vertices in $A_i$ has at most the degree of ${\alpha }_i$ and is non-adjacent to ${\alpha }_i$. Then $$e(G)\le e(T_s(n;{\alpha }_1,{\alpha }_2,..,{\alpha }_r))$$ and the equality holds iff $G=T_s(n;{\alpha }_1,{\alpha }_2,..,{\alpha }_r)$ and the sets $A_i$ are its chromatic classes. The assumption ${\alpha }_i\ge [\frac{n}{s}]$ is essential in the above two propositions. So, for $r=1$ it is not true that if ${\alpha }_1<[\frac{n}{s}]$ then the graph $T_s(n,{\alpha }_1)$ has maximal number of edges among the $n$-graph without $K_{s+1}$ and having an independant set $A_1$ with at least ${\alpha }_1$ vertices. Only the Turans graph $T_s(n)$ has maximal number of edges in this class of graphs.