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$,

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

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

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

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.




© 1996-9 Eric W. Weisstein
1999-05-26