Editing Turán graph (section)

{{Short description|Balanced complete multipartite graph}}
{{infobox graph
 | name = Turán graph
 | image = [[Image:Turan 13-4.svg|180px]]
 | image_caption = The Turán graph T(13,4)
 | namesake = [[Pál Turán]]
 | vertices = <math>n</math>
 | edges = ~<math>\left(1- \frac{1}{r}\right)\frac{n^2}{2}</math>
 | radius = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 2 & r \le n/2\\ 1 & \text{otherwise}\end{array}\right.</math>
 | diameter = <math>\left\{\begin{array}{ll}\infty & r = 1\\ 1 & r = n\\ 2 & \text{otherwise}\end{array}\right.</math>
 | girth = <math>\left\{\begin{array}{ll}\infty & r = 1 \vee (n \le 3 \wedge r \le 2)\\ 4 & r = 2\\ 3 & \text{otherwise}\end{array}\right.</math>
 | chromatic_number = <math>r</math>
 | chromatic_index =
 | notation = <math>T(n,r)</math>
}}
The '''Turán graph''', denoted by <math>T(n,r)</math>, is a [[complete multipartite graph]]; it is formed by [[partition of a set|partitioning a set]] of <math>n</math> vertices into <math>r</math> 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 <math>q</math> and <math>s</math> are the quotient and remainder of dividing <math>n</math> by <math>r</math> (so <math>n = qr + s</math>), the graph is of the form <math>K_{q+1, q+1, \ldots, q, q}</math>, and the number of edges is
:<math> \left(1 - \frac{1}{r}\right)\frac{n^2 - s^2}{2} + {s \choose 2}</math>.

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