Deriving the number of edges in a Turán graph

Question

When stating Turán's theorem, the Turán graphs are often used to give an upper bound on the possible number of edges in a graph without a clique of a certain size. This bound can also be proven explicitly (see this for different ways to state/prove the theorem).

But when the Turán graph is used, the number of its edges must be determined somehow. Wolfram gives us a number, but I really need to derive it somehow. So, again, in short: How is the number of edges in a Turán graph derived?

Answer 1

Let $T_{n,k}$ denote the Turán graph on $n$ vertices with no $(k + 1)$-clique. Then Turán's Theorem tells us that: $$ e(T_{n,k}) = \left\lfloor \left(1 - \frac{1}{k} \right)\frac{n^2}{2} \right\rfloor $$ The links you provide give several proofs as to how this expression is derived. For a less rigorous way to think about it intuitively, imagine a complete $k$-partite graph on $n$ vertices where each partite set has roughly the same number of vertices: $n/k$. Since there are $\binom{k}{2}$ distinct pairs of partite sets and for each pair we can add all $(n/k)^2$ possible edges, we obtain: $$ e(T_{n,k}) \approx \binom{k}{2} \cdot \left(\frac{n}{k} \right)^2 = \frac{k(k - 1)}{2} \cdot \frac{n^2}{k^2} = \frac{k - 1}{k} \cdot \frac{n^2}{2} = \left(1 - \frac{1}{k} \right)\frac{n^2}{2} $$

Answer 2

The Turán graph $T(n,r)$ is an $r$-partite graph whose parts are as nearly equal in size as possible. Let $n=pr+s$, where $p$ and $s$ are integers, and $0\le s<r$; then $T(n,r)$ has $s$ parts of size $p+1$ and $r-s$ parts of size $p$. Thus, $s\binom{p+1}2+(r-s)\binom{p}2$ of the $\binom{n}2$ pairs of vertices of $T(n,r)$ are within a single part and are not connected by an edge, and the number of edges of $T(n,r)$ is therefore

$$\begin{align*} \binom{n}2-s\binom{p+1}2-(r-s)\binom{p}2&=\frac{n(n-1)-sp(p+1)-(r-s)p(p-1)}2\\\\ &=\frac{n^2-s-2ps-p^2r}2\\\\ &=\frac{p^2r^2+2prs+s^2-p^2r-2ps-s}2\\\\ &=\frac{(r-1)(p^2r+2ps)}2+\binom{s}2\\\\ &=\frac{(r-1)(p^2r^2+2prs)}{2r}+\binom{s}2\\\\ &=\frac{(r-1)(n^2-s^2)}{2r}+\binom{s}2\;.\tag{1} \end{align*}$$

Contrary to the assertions in Wikipedia and MathWorld, this is not necessarily equal to

$$\left\lfloor\frac{(r-1)n^2}{2r}\right\rfloor\;,\tag{2}$$

as may be seen by considering the case $n=12,r=8$. $T(12,8)$ evidently has $4$ vertices of degree $11$ and $8$ of degree $10$, for a total of $\frac12(44+80)=62$ edges, which agrees with $(1)$, while $(2)$ evaluates to $63$. It is true, however, that

$$\frac{(r-1)(n^2-s^2)}{2r}+\binom{s}2<\frac{(r-1)n^2}{2r}$$

and hence that

$$\frac{(r-1)(n^2-s^2)}{2r}+\binom{s}2\le\left\lfloor\frac{(r-1)n^2}{2r}\right\rfloor\;,$$

since

$$\binom{s}2=\frac{s^2-s}2=\frac{rs^2-rs}{2r}<\frac{(r-1)s^2}{2r}\;.$$

A lower bound on the number of edges in $T(n,r)$ is

$$\frac{(r-1)n^2}{2r}-\frac{n}4\;.$$

Answer 3

This is a bit late, but I thought I would give an alternative to Brian M. Scott's derivation of the number of edges in the Turán graph $T(n,r)$ which involves a little more counting and a little less manipulation. I'll denote the number of edges in $T(n,r)$ by $t(n,r)$.

If $r$ evenly divides $n$, then as Adriano remarked, we have $r$ parts each of size $n/r$, and every edge between two different parts. Thus in this case, $$ t(n,r) = {r\choose 2}\bigg(\frac{n}{r}\bigg)^2 = \frac{r-1}{r}\cdot \frac{n^2}{2}. $$

Now suppose $n$ isn't evenly divisible by $r$, and let $s$ denote the remainder, so $0<s<r$, and $n-s$ is divisible by $r$. The Turán graph $T(n,r)$ consists of $T(n-s,r)$ together with $s$ "extra vertices", which are distributed so that each part of $T(n-s,r)$ gets at most one extra vertex. The number of edges in $T(n-s,r)$ is given by our formula above. Each of the extra vertices is adjacent to all of the vertices of this $T(n-s,r)$ except for those in its part, and this accounts for $\frac{r-1}{r}s(n-s)$ edges in total. Finally, the extra vertices are all adjacent to each other, which contributes ${s\choose 2}$ edges. Putting this all together, we have \begin{align*} t(n,r) &= t(n-s,r)+\frac{r-1}{r}s(n-s)+{s\choose 2}\\ &= \frac{r-1}{r}\left(\frac{(n-s)^2}{2}+s(n-s)\right)+{s\choose 2}\\ &= \frac{r-1}{r}\cdot\frac{n^2-s^2}{2}+{s\choose 2}.\\ &= \frac{r-1}{r}\cdot\frac{n^2}{2}-\frac{s(r-s)}{2r}. \end{align*}