Combinatorics Extremal combinatorics Example

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$ .

Where this leads

1 page builds on this one.

Turán's theorem

Tag	`0VTCABADBE`
URI	`m2://0VTCABADBE`
Kind	example
Writing	W2 usable
MSC	05C35
Instance of	Graph
Same as	Wikidata Q720459 Wikipedia Turán graph

Turán graph

Example

Remarks

Where this leads

Further reading

What this page needs for W3

What links here

Used by