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
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).
See also |
