# Deriving the number of edges in a Turán graph

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?

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

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, 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*}

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

• Very nice intuition! Dec 31, 2016 at 13:00
• As indicated in the other answer to this problem, the formula you mention for the number of edges of $T_{n,k}$ is not correct. It has the right order of magnitude though. Aug 14, 2018 at 4:32