Past exam of the mathematics course of the University of Cambridge / 2024 / ii / Paper 2 / 17I / Solution

The Turan theorem states that every $n$-vertex graph with no $K_{r+1}$ has at most $e(T_r(n))$ edges, where $T_r(n)$ is the complete $r$-partite graph with part sizes differing by at most one.

Here is an induction on $n$ and $r$. If a $K_{r+1}$-free graph $G$ contains no $K_r$, induction on $r$ givesOtherwise choose a copy $S$ of $K_r$. Every vertex outside $S$ has at most $r-1$ neighbors in $S$, and induction on $n$ givesThe last identity is obtained by removing one vertex from every part of $T_r(n)$. This proves the theorem; the standard equality analysis forces the balanced complete $r$-partite graph.

Now suppose $G$ is rhombus-free. If it is triangle-free, the $r=2$ case just proved gives
$e(G)\le e(T_2(n))$. Otherwise remove the three vertices of a triangle. No remaining vertex can be adjacent to two vertices of that triangle, since those two triangle vertices and the outside vertex would form a second triangle sharing an edge with the first. Induction therefore givesThis proves the rhombus-free edge bound and hence the requested strict contrapositive.

For equality at $n=6$, take the triangular prism graph: two disjoint triangles joined by a matching. It has $6+3=9=e(T_2(6))$ edges. Every edge belongs to at most one triangle, so there is no rhombus, while the presence of triangles proves that it is not isomorphic to $T_2(6)=K_{3,3}$.

Solved by gpt-5.6-sol high.