A Turán graph, sometimes called a maximally saturated graph (Zykov 1952, Chao and Novacky 1982), with positive integer parameters 
and 
is a type of extremal graph on 
vertices originally considered by Turán (1941). There
are unfortunately two different conventions for the index 
.
In the more standard terminology (and that adopted here), the 
-Turán graph, sometimes also called a K-graph and
variously denoted 
,
(Gross and Yellen 2006, p. 476),
(Chao and Novacky 1982), or 
(Pach and Agarwal 1995, p. 120),
is the extremal graph on 
graph vertices that contains
no 
-clique
for 
(Chao and Novacky 1982;
Diestel 1997, p. 149; Bollobás 1998, p. 108). In other words, the
Turán graph has the maximum possible number of graph
edges of any 
-vertex
graph not containing a complete graph 
. The Turán graph is also the complete 
-partite graph on 
vertices whose partite sets are as nearly equal in cardinality
as possible (Gross and Yellen 2006, p. 476).
Unfortunately, some authors, including Skiena (1990, pp. 143-144), Aigner (1995), and Pemmaraju and Skiena (2003, pp. 247-248), use the convention that the 
-Turán graph contains no 
-clique (instead
of 
-clique),
meaning that the 
-Turán
graph of these authors is the 
-Turán graph as defined above.
The Turán graph on 
vertices that does not contain the complete graph 
can be generated in the Wolfram
Language using TuranGraph[n,
k] and precomputed properties are available using GraphData[
"Turan", 
n, k
].
Turán graphs may be obtained by dividing a set of graph vertices 
into 
pairwise disjoint subsets with graph
vertices of degree 
,
..., 
, satisfying
 |
(1)
|
and with two graph vertices joined iff they lie in distinct graph vertex sets. Such graphs
are sometimes denoted 
.
They can be directly constructed by numbering the vertices 0, 1, ..., 
and connecting vertices by an edge iff
when the vertices are incongruent modulo 
(König 1936, Chao and Novacky 1982).
Turán's theorem gives the number of edges 
for the 
-Turán graph as
 |
(2)
|
where 
denotes the floor function. This gives the triangle
 |
(3)
|
(OEIS A193331).
Turán graphs are chromatically unique (Chao and Novacky 1982). A Turán graph 
is always strongly
regular if 
(but may be regular even if 
).
The chromatic number of 
is 
(Chao and Novacky 1982).
Special cases of Turán graphs are summarized in the following table.
| graph class | Turán graph |
complete graph  |  |
 |  |
complete
bipartite graph  |  |
 -cocktail party graph |  |
complete tripartite graph  |  |
empty
graph  |  |
The Turán graph ![T(n,[n/3])](/images/equations/TuranGraph/Inline55.svg)
has 
maximal cliques where 
and 
, the largest number possible among all 
-vertex graphs (Moon and Moser 1965).
