# An important inequality for k-partite graphs

As you come across this link: A Complete k-partite Graph

You'll be noted that a k-partite has atmost $\frac{n^{2}(k-1)}{2k}$ edges where $n=V(G)$, but how to actually show this, i.e., to show any k-partite graph must either have less edges than or atmost equal number of edges as the Turan Graph $T_m,_n$ has.

## 2 Answers

Looking at the answer in the post you linked, Kaya left out some algebraic details and an explanation why that expression is maximized when the partite sets are balanced. I would guess this is what is giving you trouble. Instead of filling the algebraic details in, I will use a more combinatorial approach and prove that there is no $k$-partite graph on $n$ vertices with more edges than the Turan Graph $T(n,k)$.

To see this, assume to the contrary that there is a $k$-partite graph with more edges than $T(n,k)$, and let $G$ be the largest such one. Then $G$ is a complete $k$-partite graph since otherwise $G$ is not the largest one. Let $A$ and $B$ be the biggest and smallest partite set in $G$ respectively. Since $G$ is not $T(n,k)$, $|A|-|B|\geq 2$. Let $x\in A$.

Consider $G'$ the complete $k$-partite graph with partite sets identical to $G$ except with $A'=A\setminus \{x\}$ and $B'=B\cup\{x\}$ in place of $A$ and $B$. Notice that the only difference between $G$ and $G'$ is that $G$ has $|B|$ edges from $x$ to $B$ and $G$ is missing $|A'|=|A|-1$ edges from $x$ to $A'$. Then

\begin{align} E(G)-E(G')&=|B|-(|A|-1)\\ &=1-(|A|-|B|)\\ &\leq -1. \end{align}

Then $G'$ is a $k$-partite graph on $n$ vertices with even more edges than $G$, contradicting the maximality of $G$.

Thus, there does not exist a graph with more edges than $T(n,k)$.

Maybe I'm misunderstanding your question, but doesn't the link you mention show how to arrive at that inequality?

*not an answer because I have less than 50 rep.

• Yes, somehow, but Kaya didn't explain why that k-partite graph has its max edges if the partitions are well-balanced. – Ashkan Ranjbar Dec 17 '16 at 22:28