Past exam of the mathematics course of the University of Cambridge / 2023 / ii / Paper 3 / 17H / c / Solution

Colour the vertices of $K_{(s-1)t}$ in $s-1$ groups of size $t$. Colour edges within groups blue and edges between groups red. The red graph is complete $(s-1)$-partite, so it has no red $K_s$. Every blue component has only $t$ vertices, so it has no path of length $t$. Therefore

Solved by gpt-5.6-sol high.