Past exam of the mathematics course of the University of Cambridge / 2020 / ii / Paper 3 / 17G (Graph Theory)

Turan theorem states that among all $N$-vertex graphs containing no $K_{r+1}$, the maximum number of edges is attained by the Turan graph $T_r(N)$, the complete multipartite graph whose $r$ part sizes differ by at most one.

Here is the Zykov symmetrization proof. Start with an extremal $K_{r+1}$-free graph. If nonadjacent vertices $u,v$ have different neighbourhoods, replace the lower-degree vertex by a clone of the higher-degree one: delete all its incident edges and join it to precisely the neighbours of the other vertex. This does not decrease the number of edges and cannot create a $K_{r+1}$, because a clique using the clone corresponds to one using the original vertex. Repeating the operation, with the standard tie-breaking that merges equal-neighbourhood classes, produces a complete multipartite extremal graph. It has at most $r$ nonempty parts, since choosing one vertex from each part gives a clique.

If two part sizes satisfy $a\ge b+2$, moving one vertex from the larger part to the smaller changes the number of cross-edges byThus an extremal partition has exactly $r$ parts whose sizes differ by at most one. This is $T_r(N)$ and proves the theorem. For $r=2$ it is Mantel theorem: a triangle-free graph on $N$ vertices has at most $\lfloor N^2/4\rfloor$ edges.

Here $|V(G)|=2n$ and $e(G)=n^2+1$. By Mantel theorem, a triangle-free graph of this order has at mostedges, so $G$ contains a triangle in a graph.

If $n=2$, then $G$ has four vertices and five of the six possible edges, so it is $K_4$ with one edge deleted. Exactly the two triangles containing neither both endpoints of the deleted edge remain. Hence $G$ contains two triangles.

Let $t(G)$ be the number of triangles in a graph. Count incidences $(e,\Delta )$ in which the edge $e$ lies in the triangle $\Delta$. Every edge contributes at least one incidence by hypothesis, while every triangle contributes exactly three. ThereforeThis is the edge-triangle incidence bound.

If the edge $uv$ lies in no triangle, no vertex can be adjacent to both endpoints; hence the neighbourhoods satisfy $\Gamma (u)\cap \Gamma (v)=\varnothing$.

Suppose $|\Gamma (u)|+|\Gamma (v)|=2n$. The two disjoint neighbourhoods then partition $V(G)$. If both were independent, every edge would run between these two parts, so $G$ would be bipartite andcontrary to $e(G)=n^2+1$. Thus at least one neighbourhood contains an edge, and that edge forms a triangle with $u$ or $v$.

We now prove by induction on $n\ge 2$ the Triangle lower bound one edge above the Mantel threshold: every graph on $2n$ vertices with at least $n^2+1$ edges has at least $n$ triangles. Part (ii) is the base case. For $n\ge 3$, if every edge lies in a triangle, part (iii) givesOtherwise choose an edge $uv$ lying in no triangle and put $s=d(u)+d(v)\le 2n$. Deleting $u,v$ removes $s-1$ edges, so the graph $G^{\prime }=G-u-v$ hasIf $s=2n$, induction gives at least $n-1$ triangles in $G^{\prime }$, while the nonindependence proved above supplies a further triangle through $u$ or $v$.

If $s\le 2n-1$, then $e(G^{\prime })\ge (n-1{)}^2+2$. Induction first supplies a triangle $\Delta$ in $G^{\prime }$. Delete one edge of $\Delta$; the remaining graph still has at least $(n-1{)}^2+1$ edges, so induction supplies $n-1$ triangles avoiding that edge. Together with $\Delta$, these give at least $n$ distinct triangles in $G$.