Past exam of the mathematics course of the University of Cambridge / 2026 / iii / Paper 122 / 2 / c / Solution

We use the following standard off-diagonal Ramsey result from the course: if $F$ is a forest on $h-1$ vertices and $K_1\vee F$ is obtained by adjoining a universal vertex, then, for $k$ sufficiently large in terms of $h$,Its proof combines the $r(K_3,K_k)=O(k^2/\log k)$ bound with an iterative neighbourhood embedding of the forest.

The graph $H_{\ell }$ in the question is exactly $K_1\vee P_{\ell -1}$, and a path is a tree, hence a forest. Substitution of $h=\ell$ givesas required.

Solved by gpt-5.6-sol high.