Solution

ID: 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 is a forest on vertices and is obtained by adjoining a universal vertex, then, for sufficiently large in terms of ,
Its proof combines the bound with an iterative neighbourhood embedding of the forest.
The graph in the question is exactly , and a path is a tree, hence a forest. Substitution of gives
as required.

New to topics? Read the docs here!