combinatoricsextremal-graph-theorygraph theory
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?
Lemma. If $G$ has $n$ vertices, $m$ edges, and $t$ triangles, and $F$ is a forest on the same vertex set (edge-disjoint from $G$, without loss of generality), then $F \cup G$ has at most $t + 3m$ triangles.
Proof. There are, of course, $t$ triangles with all three edges in $G$.
There are at most $m$ triangles with one edge from $G$ and two edges from $F$. That's because for every edge $uv \in E(G)$, $F$ has at most one $u,v$-path of length $2$: it has at most one $u,v$-path of any length!
Finally, there are fewer than $2m$ triangles with two edges from $G$ and one edge from $F$. To see this, let $v$ be any vertex; there are fewer than $\deg_G(v)$ edges of $F$ in $N_G(v)$, so there are fewer than $\deg_G(v)$ triangles with two edges from $G$ incident to $v$, and one edge of $F$. Sum over all vertices $v$, and we get less than $2m$. $\square$
By induction with this lemma, we see that the union of $\alpha$ forests has at most $3 \binom{\alpha}{2}(n-1) = O(\alpha^2 n)$ triangles.
Asymptotically, this is matched by the union of $\alpha$ stars centered at $\alpha$ different vertices, which has $\binom \alpha 3 + \binom \alpha 2 (n-\alpha) = \Omega(\alpha^2 n)$ triangles.
Though we can think of the graph in question,
as $5$ tetrahedrons glued together, it is more profitable to think of it as $C_5 + K_2$, where $+$ denotes graph join: we take disjoint copies of $C_5$ and $K_2$, and draw all the edges between them. In the diagram, $C_5$ is the $5$ outside vertices, and $K_2$ is the two center vertices.
Similarly, the graph $C_5 + K_n$ has chromatic number $n+3$ (you need $3$ colors to color $C_5$, and $n$ separate colors to color $K_n$) and clique number $n+2$ (at most two vertices from $C_5$, plus at most $n$ vertices from $K_n$, can be part of a clique). So $C_5 + K_{k-3}$ is a graph with the property you want.
In fact, it is the smallest such graph. $C_5 + K_{k-3}$ has $k+2$ total vertices, so there's only a few cases to check:
The argument is basically the same as for $C_5 + K_2$.
Best Answer
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\;.$$