Editing Turán graph (section)

==Special cases==
[[File:Complex tripartite graph octahedron.svg|thumb|150px|The [[octahedron]], a 3-[[cross polytope]] whose edges and vertices form ''K''<sub>2,2,2</sub>, a Turán graph ''T''(6,3). Unconnected vertices are given the same color in this face-centered projection.]]
Several choices of the parameter ''r'' in a Turán graph lead to notable graphs that have been independently studied.

The Turán graph ''T''(2''n'',''n'') can be formed by removing a [[perfect matching]] from a [[complete graph]] ''K''<sub>2''n''</sub>. As {{harvtxt|Roberts|1969}} showed, this graph has [[boxicity]] exactly ''n''; it is sometimes known as the ''Roberts graph''.{{sfnp|Roberts|1969}} This graph is also the 1-[[Skeleton (topology)|skeleton]] of an ''n''-dimensional [[cross-polytope]]; for instance, the graph ''T''(6,3)&nbsp;=&nbsp;''K''<sub>2,2,2</sub> is the [[octahedral graph]], the graph of the regular [[octahedron]]. If ''n'' couples go to a party, and each person shakes hands with every person except his or her partner, then this graph describes the set of handshakes that take place; for this reason, it is also called the '''cocktail party graph'''.

The Turán graph ''T''(''n'',2) is a [[complete bipartite graph]] and, when ''n'' is even, a [[Moore graph]]. When ''r'' is a divisor of ''n'', the Turán graph is [[Symmetric graph|symmetric]] and [[Strongly regular graph|strongly regular]], although some authors consider Turán graphs to be a trivial case of strong regularity and therefore exclude them from the definition of a strongly regular graph.

The class of Turán graphs can have exponentially many maximal cliques, meaning this class does not have [[Graphs with few cliques|few cliques]]. For example, the Turán graph <math>T(n,\lceil n/3\rceil)</math> has 3<sup>''a''</sup>2<sup>''b''</sup> [[maximal clique]]s, where
3''a''&nbsp;+&nbsp;2''b''&nbsp;=&nbsp;''n'' and ''b''&nbsp;≤&nbsp;2; each maximal clique is formed by choosing one vertex from each partition subset. This is the largest number of maximal cliques possible among all ''n''-vertex graphs regardless of the number of edges in the graph; these graphs are sometimes called '''Moon–Moser graphs'''.{{sfnp|Moon|Moser|1965}}