info prev up next book cdrom email home

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

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


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

© 1996-9 Eric W. Weisstein