Let be a graph with graph vertices and graph edges on graph vertices without a -clique. Thenwhere is the 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 defined as the unique graph without a -clique having the maximum possible number of graph edges, namelywhere denotes the floor function.
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..