Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 130 / 1 / i

Write $\mathbb{N}=\{1,2,\dots \}$ and let $\chi$ be the given finite coloring of the edges of the complete graph on the positive integers. Construct an increasing sequence $(v_i)$ and nested infinite sets $A_0\supset A_1\supset \cdots$ as follows. Set $A_0=\mathbb{N}$. Having chosen $A_{i-1}$, take $v_i=\min A_{i-1}$, partition $A_{i-1}\setminus \{v_i\}$ by the color of $\{v_i,w\}$, and use the infinite pigeonhole principle to choose an infinite set $A_i$ on which this color is constant, say $r_i$. Every element of $A_i$ exceeds $v_i$.

The infinite pigeonhole principle applied again to $(r_i)$ gives an infinite set of indices $I$ and a color $r$ such that $r_i=r$ for all $i\in I$. For $i<j$ in $I$, nesting gives $v_j\in A_i$, so $\chi (\{v_i,v_j\})=r$. Thus the infinite set $X=\{v_i:i\in I\}$ 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.