Past exam of the mathematics course of the University of Cambridge / 2022 / ii / Paper 2 / 17F (Graph Theory)

The extremal number $\mathrm{ex}(n,H)$ is the maximum number of edges in an $n$-vertex graph containing no subgraph isomorphic to $H$.

Let $G$ be triangle-free with $e$ edges. For every edge $uv$, the neighbourhoods of $u$ and $v$ are disjoint apart from their endpoints, so
$d(u)+d(v)\le n$. Summing over edges and applying Cauchy-Schwarz inequality giveswhileThus $e\le n^2/4$, proving the required Mantel theorem bound.

Let $T$ be the number of triangles. Each edge $uv$ has at least
$d(u)+d(v)-n$ common neighbours, and summing common-neighbour counts over edges counts every triangle three times. HenceIf $e>(1+\delta )n^2/4$, this is greater than
$\delta en>\delta n^3/4$. Thereforeso one may take $\epsilon =\delta /12$.

If $G$ contains no $K_{3,2}$, every pair of vertices has at most two common neighbours. Double-counting a vertex together with an unordered pair of its neighbours givesConsequentlyBy Cauchy--Schwarz,This quadratic inequality implies $e<c{n}^{3/2}$ for an absolute constant $c$; for example $c=2$ works for every $n\ge 1$. Thus

Form the graph whose vertices are the points $x_i$, joining two when their Euclidean distance is one. Two distinct points have at most two common unit-distance neighbours, because two unit circles intersect in at most two points. The graph is therefore $K_{3,2}$-free. Part (c) bounds its unordered edges by $2n^{3/2}$, so the number of ordered unit-distance pairs is at most