Turán graph

Example

Let $n \ge r \ge 1$ be integers. The Turán graph $T(n, r)$ has $n$ vertices, split into $r$ parts whose sizes differ by at most $1$. Two vertices are adjacent if and only if they are in different parts.

Remarks

Two vertices in the same part are not adjacent. Among any $r + 1$ vertices, two are in the same part, so $T(n, r)$ has no clique with $r + 1$ vertices. The number of edges of $T(n, r)$ is $\left\lfloor \left(1 - \frac{1}{r}\right) \frac{n^2}{2} \right\rfloor$. $T(n, 2)$ is the complete bipartite graph $K_{\lfloor n/2 \rfloor, \lceil n/2 \rceil}$, and $T(n, n)$ is the complete graph $K_n$.

Explanations

L1 human

To build $T(n, r)$, split $n$ people into $r$ teams of almost equal size, and join two people when they are in different teams. It is the graph with the most edges that has no clique of size $r + 1$.