Paper 2, Section II, G

Graph Theory
Part II, 2016

Define the Turán graph Tr(n)T_{r}(n), where rr and nn are positive integers with nrn \geqslant r. For which rr and nn is Tr(n)T_{r}(n) regular? For which rr and nn does Tr(n)T_{r}(n) contain T4(8)T_{4}(8) as a subgraph?

State and prove Turán's theorem.

Let x1,,xnx_{1}, \ldots, x_{n} be unit vectors in the plane. Prove that the number of pairs i<ji<j for which xi+xjx_{i}+x_{j} has length less than 1 is at most n2/4\left\lfloor n^{2} / 4\right\rfloor.