Turán Graph

The $(n,k)$-Turán graph is the Extremal Graph on $n$ Vertices which contains no $k$-Clique. In other words, the Turán graph has the maximum possible number of Edges of any $n$-vertex graph not containing a Complete Graph $K_k$. Turán's Theorem gives the maximum number of edges $t(n,k)$ for the $(n,k)$-Turán graph. For $k=3$,

$$t(n,3)={\textstyle{1\over 4}}n^2,$$

so the Turán graph is given by the Complete Bipartite Graphs

$$\cases{ K_{n/2, n/2} & $n$\ even\cr K_{(n-1)/2, (n+1)/2} & $n$\ odd.\cr}$$

See also Clique, Complete Bipartite Graph, Turán's Theorem

References

Aigner, M. ``Turán's Graph Theorem.'' Amer. Math. Monthly 102, 808-816, 1995.