turan_graph(n, r)[source]

Return the Turan Graph

The Turan Graph is a complete multipartite graph on \(n\) vertices with \(r\) disjoint subsets. It is the graph with the edges for any graph with \(n\) vertices and \(r\) disjoint subsets.

Given \(n\) and \(r\), we generate a complete multipartite graph with \(r-(n \mod r)\) partitions of size \(n/r\), rounded down, and \(n \mod r\) partitions of size \(n/r+1\), rounded down.

  • n (int) – The number of vertices.
  • r (int) – The number of partitions. Must be less than or equal to n.


Must satisfy \(1 <= r <= n\). The graph has \((r-1)(n^2)/(2r)\) edges, rounded down.