Past exam of the mathematics course of the University of Cambridge 2019 ii Paper 2 17G b Solution 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 .