 Turán graph

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$.^[ref]

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: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\cdot 3\cdot 2=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\mathrm{mod}r$ is the remainder, with $0\le s<r$. There are $s$ parts of size $q+1$ and $r-s$ of size $q$. For any part sizes $a_1,\dots ,a_r$ summing to $n$, count cross edges by expanding the square:ThereforeFor $n=8,r=3$, we have $q=2,s=2$, giving $(64-2\cdot 9-1\cdot 4)/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\ge b+2$, moving one vertex from the larger part to the smaller decreases their contribution to the sum of squares byso 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.

The Turán graph, denoted as \( T(n, r) \), is a specific type of graph used in extremal graph theory, which studies the conditions under which graphs contain certain subgraphs. The Turán graph is designed to be the largest \( K_{r+1} \)-free graph (a graph that does not contain a complete subgraph of \( r+1 \) vertices) with \( n \) vertices.