= Turán graph
{c}
{title2=$T_r(n)$}
{wiki}
The Turán graph $T_r(n)$ is a <complete multipartite graph> with $r$ <independent sets> of sizes differing by at most one, with every cross <edge> present. Empty parts are allowed when $r>n$.<Graph Theory by Reinhard Diestel>[third electronic edition (2005), §7.1, printed p. 165, definition of Turán graphs and convention for empty partition sets]{ref}
\Image[/turan-balanced-tripartite-edge-count.png]
{title=The <Turán graph> $T_3(8)$ has three <independent sets> of sizes $3,3,2$, giving $21$ <edges> and no four-<vertex> <clique>}
In this example, the <independent sets> are $A=\{a_1,a_2,a_3\}$, $B=\{b_1,b_2,b_3\}$ and $C=\{c_1,c_2\}$. Count the <edges> between each pair of parts:
$$
t_3(8)=3\cdot3+3\cdot2+3\cdot2=9+6+6=21.
$$
Any four <vertices> put at least two in the same <independent set>, by the <pigeonhole principle>, so they cannot form $K_4$. Conversely, every choice of one <vertex> from each part is a <triangle in a graph>, giving $3\cdot3\cdot2=18$ <triangles in a graph>. <Clique> exclusion here does not mean <triangle-free>.
For the exact count, <Euclidean division> writes $n=rq+s$, where $q=\lfloor n/r\rfloor$ uses the <floor function> and $s=n\bmod r$ is the <remainder>, with $0\leq s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\ldots,a_r$ summing to $n$, count cross <edges> by expanding the square:
$$
e(K_{a_1,\ldots,a_r})=\sum_{i<j}a_i a_j=\frac12\left(n^2-\sum_{i=1}^r a_i^2\right).
$$
Therefore
$$
t_r(n)=\frac12\left[n^2-s(q+1)^2-(r-s)q^2\right]
=\left(1-\frac1r\right)\frac{n^2}{2}-\frac{s(r-s)}{2r}.
$$
For $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot9-1\cdot4)/2=21$. The <Quadratic Turan edge bound> gives $64/3$ instead: the exact correction subtracts $1/3$.
Balancing is an <integer> optimization with a simple reason. If two part sizes satisfy $a\geq b+2$, moving one <vertex> from the larger part to the smaller decreases their contribution to the <sum of squares> by
$$
a^2+b^2-(a-1)^2-(b+1)^2=2(a-b-1)>0,
$$
so it increases the <edge> count by $a-b-1$. For eight <vertices>, parts $4,2,2$ give $20$ <edges>; moving one <vertex> produces $3,3,2$ and $21$ <edges>. The most symmetric permitted sizes pack the most cross <edges>, which explains the sharp construction in <Turán's theorem>.
Back to article page
