Turán graph

Turán graph
The Turán graph T(13,4)
Named after	Pál Turán
Vertices	${\displaystyle n}$
Edges	~${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}}$
Radius	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\2&r\leq n/2\\1&{\text{otherwise}}\end{array}}\right.}$
Diameter	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\\1&r=n\\2&{\text{otherwise}}\end{array}}\right.}$
Girth	${\displaystyle \left\{{\begin{array}{ll}\infty &r=1\vee (n\leq 3\wedge r\leq 2)\\4&r=2\\3&{\text{otherwise}}\end{array}}\right.}$
Chromatic number	${\displaystyle r}$
Notation	${\displaystyle T(n,r)}$
Table of graphs and parameters

The Turán graph, denoted by ${\displaystyle T(n,r)}$, is a complete multipartite graph; it is formed by partitioning a set of ${\displaystyle n}$ vertices into ${\displaystyle r}$ subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where ${\displaystyle q}$ and ${\displaystyle s}$ are the quotient and remainder of dividing ${\displaystyle n}$ by ${\displaystyle r}$ (so ${\displaystyle n=qr+s}$), the graph is of the form ${\displaystyle K_{q+1,q+1,\ldots ,q,q}}$, and the number of edges is

${\displaystyle \left(1-{\frac {1}{r}}\right){\frac {n^{2}-s^{2}}{2}}+{s \choose 2}}$.

For ${\displaystyle r\leq 7}$, this edge count can be more succinctly stated as ${\displaystyle \left\lfloor \left(1-{\frac {1}{r}}\right){\frac {n^{2}}{2}}\right\rfloor }$. The graph has ${\displaystyle s}$ subsets of size ${\displaystyle q+1}$, and ${\displaystyle r-s}$ subsets of size ${\displaystyle q}$; each vertex has degree ${\displaystyle n-q-1}$ or ${\displaystyle n-q}$. It is a regular graph if ${\displaystyle n}$ is divisible by ${\displaystyle r}$ (i.e. when ${\displaystyle s=0}$).