Proof of Ramsey's theorem by induction on r + s

Proof

We argue by induction on $r + s$. Call a positive integer $n$ good for $(r, s)$ if the following holds. Every colouring of the edges of $K_n$ in blue and red has a blue clique with $r$ vertices or a red clique with $s$ vertices. We show that some $n$ is good for $(r, s)$.

1. If $n$ is good for $(r, s)$, then every $n' \ge n$ is good for $(r, s)$. Indeed, a colouring of $K_{n'}$ restricts to a colouring of the complete graph on any $n$ of its vertices. A clique there is a clique in $K_{n'}$.
2. Base case: $r = 1$ or $s = 1$. A single vertex is a clique with $1$ vertex, and it is blue and red, since it has no edges. So $n = 1$ is good for $(r, s)$.
3. Induction step: let $r, s \ge 2$, and suppose the claim holds for all pairs with a smaller sum. Let $n_1$ be good for $(r - 1, s)$, and let $n_2$ be good for $(r, s - 1)$.
4. Let $n = n_1 + n_2$, and colour the edges of $K_n$ blue or red. Fix a vertex $v$.
5. Let $B$ be the set of vertices joined to $v$ by a blue edge, and $R$ the set joined to $v$ by a red edge. Then $\abs{B} + \abs{R} = n - 1 = n_1 + n_2 - 1$.
6. So $\abs{B} \ge n_1$ or $\abs{R} \ge n_2$. Otherwise $\abs{B} + \abs{R} \le (n_1 - 1) + (n_2 - 1) < n_1 + n_2 - 1$.
7. Case $\abs{B} \ge n_1$. The vertices of $B$ span a complete graph with at least $n_1$ vertices. By Step 1 and the choice of $n_1$, it has a blue clique with $r - 1$ vertices or a red clique with $s$ vertices.
8. A red clique with $s$ vertices in $B$ is what we want. Let $S \subseteq B$ be a blue clique with $r - 1$ vertices. All edges from $v$ to $B$ are blue, so $S \cup \set{v}$ is a blue clique with $r$ vertices.
9. Case $\abs{R} \ge n_2$. In the same way, $R$ contains a blue clique with $r$ vertices or a red clique $T$ with $s - 1$ vertices. In the second case, $T \cup \set{v}$ is a red clique with $s$ vertices.
10. So $n = n_1 + n_2$ is good for $(r, s)$. By induction, for all positive integers $r$ and $s$, some positive integer $n$ is good for $(r, s)$.