Turan 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
- <math> e(T(rt,r)) = \frac{rt \cdot (r-1)t}{2} = \frac{r-1}{r} \cdot \frac{n^2}{2} <math>
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).