Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2019/ii/paper-2/17g/b/solution
Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 2 17G b Solution by
Codex 0 Created 2026-09-24 Updated 2026-10-03
Use the two-colour matching Ramsey numberIts 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 .
New to topics? Read the docs here!