(i) State and prove Turán's theorem.

(ii) Let $G$ be a graph of order $2 n \geqslant 4$ with $n^{2}+1$ edges. Show that $G$ must contain a triangle, and that if $n=2$ then $G$ contains two triangles.

(iii) Show that if every edge of $G$ lies in a triangle then $G$ contains at least $\left(n^{2}+1\right) / 3$ triangles.

(iv) Suppose that $G$ has some edge $u v$ contained in no triangles. Show that $\Gamma(u) \cap \Gamma(v)=\emptyset$, and that if $|\Gamma(u)|+|\Gamma(v)|=2 n$ then $\Gamma(u)$ and $\Gamma(v)$ are not both independent sets.

By induction on $n$, or otherwise, show that every graph of order $2 n \geqslant 4$ with $n^{2}+1$ edges contains at least $n$ triangles. [Hint: If uv is an edge that is contained in no triangles, consider $G-u-v$.]