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 $n \ geq s \geq 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| \leq 1$ for each pair $i,j:r <i <j \leq 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(r\ geq 0)$ be natural numbers and $n \geq s \geq r, \alpha_1+\alpha_2+..+\alpha_r \leq n, \hspace{0.2cm} \alpha_i \geq [\frac{n}{s}], \hspace{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, \hspace{0.2cm} |A_i|\geq \alpha_i, i=1,2,..,r$. Then $$e(G) \leq 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(r\ geq 1)$ be natural numbers, $n \geq s \geq r, \hspace{0.2cm} \alpha_1+\alpha_2+..+\alpha_r\leq n, \hspace{0.2cm} \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|\geq \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)\leq 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 \geq [\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.