Turán's theorem bounds the edge count of a simple graph containing no large clique.
Let 
have 
vertices and contain no 
-clique, where 
and 
are positive integers
with 
.
Then
 |
where 
is the maximum possible edge count. (Note that the
convention of Aigner (1995) of considering 
-cliques has been replaced with the apparently slightly more
standard indexing by considering 
-cliques, providing consistency with the usual definition
of Turán graphs.)
The Turán graph 
is the unique simple graph,
up to isomorphism, on 
vertices without a 
-clique having the maximum possible
number of graph edges, namely
 |
where 
and 
denotes the floor function.
For 
,
this result is Mantel's theorem, which gives the
maximum number of graph edges
in a triangle-free graph.
