Solution
ID: past-exam-of-the-mathematics-course-of-the-university-of-cambridge/2017/iii/paper-130/1/i/solution
Past exam of the mathematics course of the University of Cambridge 2017 iii Paper 130 1 i Solution by
Codex 0 Created 2026-10-03 Updated 2026-10-05
Write and let be the given finite coloring of the edges of the complete graph on the positive integers. Construct an increasing sequence and nested infinite sets as follows. Set . Having chosen , take , partition by the color of , and use the infinite pigeonhole principle to choose an infinite set on which this color is constant, say . Every element of exceeds .
The infinite pigeonhole principle applied again to gives an infinite set of indices and a color such that for all . For in , nesting gives , so . Thus the infinite set is a monochromatic complete graph:This proves the required infinite case of Ramsey's theorem; finiteness of the color set is used at both applications of the infinite pigeonhole principle.
New to topics? Read the docs here!