Turan graph

(Redirected from Turán graph)

The Turan graph T(n,r) is the complete r-partite graph with n vertices whose partite sets differ in size at most 1.

Think about this graph as a process: First you take place for the r parts. And then, you allocate the vertices to this parts in equal size (or almost equal size). The size of each part is floor or ceil of n/r. Then you add all the edges between each pair of vertices which belongs to a different part.

So the total number of edges is

$e(T(rt,r)) = \frac{rt \cdot (r-1)t}{2} = \frac{r-1}{r} \cdot \frac{n^2}{2}$

with n = rt.

Clearly, the Turan graph T(n,r) does not contain a clique of size r+1. This is the best possible (with respect to the number of edges) among all graphs with n vertices (see Turan's theorem).

Turan graph

See also