Past exam of the mathematics course of the University of Cambridge 2024 ii Paper 2 17I Solution Created 2026-09-23 Updated 2026-09-25
The Turan theorem states that every -vertex graph with no has at most edges, where is the complete -partite graph with part sizes differing by at most one.
Here is an induction on and . If a -free graph contains no , induction on givesOtherwise choose a copy of . Every vertex outside has at most neighbors in , and induction on givesThe last identity is obtained by removing one vertex from every part of . This proves the theorem; the standard equality analysis forces the balanced complete -partite graph.
Now suppose is rhombus-free. If it is triangle-free, the case just proved gives
. 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.
. 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.