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.


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.

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.