Solution

ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-2/17g/b/solution

Use the two-colour matching Ramsey number
Its upper bound follows by induction on . If there is a blue edge, remove its endpoints and apply the induction hypothesis to the remaining : it contains either a red -edge matching or a blue -edge matching, and in the latter case the removed edge completes a blue -edge matching. If there is no blue edge, the graph itself contains a red -edge matching. For , this gives the required monochromatic matching in .
The result never remains true for , including . Partition its vertices into and with and . Colour edges within blue and every other edge yellow. A blue matching has at most edges, while every yellow edge meets , so a yellow matching also has at most edges.

New to topics? Read the docs here!