[proofplan] We induct on $s + t$, proving simultaneously that $R(s, t)$ exists and satisfies the recurrence $R(s,t) \leq R(s-1,t) + R(s,t-1)$. The base cases $s = 2$ and $t = 2$ follow from the observation that $R(2, t) = t$: either some edge is red (giving a red $K_2$) or every edge is blue (giving a blue $K_t$). For the inductive step, given $s, t > 2$, set $a = R(s-1, t)$ and $b = R(s, t-1)$ (which exist by induction), and let $n = a + b$. Fix any 2-colouring of $E(K_n)$ and any vertex $x$. Among the $n - 1 = a + b - 1$ edges at $x$, pigeonhole gives either $\geq a$ red edges or $\geq b$ blue edges; each case recurses into one of the two smaller Ramsey instances and produces the desired monochromatic clique together with $x$ or independently. [/proofplan] [step:Set up induction on $s + t$ and handle the base cases] We prove by induction on $s + t \geq 4$ the statement: for all $s, t \geq 2$, the Ramsey number $R(s, t)$ exists — i.e. there is a least positive integer $N$ such that every 2-edge-colouring $c : E(K_N) \to \{\text{red}, \text{blue}\}$ contains a red $K_s$ or a blue $K_t$ — and moreover $R(s, t) \leq R(s-1, t) + R(s, t-1)$ for $s, t \geq 3$. **Base case $s = 2$** (any $t \geq 2$). We claim $R(2, t) = t$. First, $R(2, t) \leq t$: in any 2-colouring of $E(K_t)$, either some edge is red — yielding a red $K_2$ — or every edge is blue, in which case $K_t$ itself is a blue $K_t$. Second, $R(2, t) \geq t$: the colouring of $K_{t-1}$ assigning every edge blue contains no red $K_2$ (no edge is red) and no blue $K_t$ (there are only $t - 1$ vertices). Hence $R(2, t) = t$ exists. **Base case $t = 2$** (any $s \geq 2$). By the symmetry $R(s, t) = R(t, s)$ (swap the roles of red and blue), $R(s, 2) = R(2, s) = s$. In particular, these base cases cover all pairs with $s + t = 4$, namely $(s, t) = (2, 2)$, and all pairs with $\min(s, t) = 2$. [guided] The theorem asserts two things: existence of $R(s, t)$ for all $s, t \geq 2$, and the recurrence. A natural inductive parameter is $s + t$, since the recurrence reduces $R(s, t)$ to instances $R(s-1, t)$ and $R(s, t-1)$ whose sums are $s + t - 1$. **Base cases.** When $s = 2$ or $t = 2$, the recurrence does not apply (it would refer to $R(1, \cdot)$, which is not defined here), so these cases must be verified directly. *Why $R(2, t) = t$:* a red $K_2$ is just a single red edge. In $K_t$, either at least one edge is red — done — or every edge is blue, and then the entire $K_t$ is a blue $K_t$. So $N = t$ works, showing $R(2, t) \leq t$. To see this is tight, colour every edge of $K_{t-1}$ blue; there are no red edges so no red $K_2$, and the total number of vertices is $t - 1 < t$ so no blue $K_t$. *Why $R(s, 2) = s$:* swap "red" and "blue" throughout. A red $K_s$ in the new colouring corresponds to a blue $K_s$ in the original, and vice versa. This symmetry gives $R(s, 2) = R(2, s) = s$. [/guided] [/step] [step:Set up the inductive step with $n = R(s-1, t) + R(s, t-1)$] Let $s, t \geq 3$ and suppose the theorem holds for all pairs $(s', t')$ with $s' + t' < s + t$ and $s', t' \geq 2$. Define \begin{align*} a &= R(s - 1, t), & b &= R(s, t - 1), & n &= a + b. \end{align*} Both $a$ and $b$ exist by the inductive hypothesis, since $(s - 1) + t = s + t - 1 < s + t$ and $s + (t - 1) = s + t - 1 < s + t$, and both have $\min \geq 2$ because $s - 1 \geq 2$ and $t - 1 \geq 2$. We claim that every 2-edge-colouring $c : E(K_n) \to \{\text{red}, \text{blue}\}$ contains a red $K_s$ or a blue $K_t$. This will show both that $R(s, t)$ is well-defined (with value $\leq n$) and that $R(s, t) \leq a + b$, i.e. the recurrence. Fix such a colouring $c$ and a vertex $x \in V(K_n)$. Let \begin{align*} N_r(x) &= \{v \in V(K_n) \setminus \{x\} : c(x v) = \text{red}\}, \\ N_b(x) &= \{v \in V(K_n) \setminus \{x\} : c(x v) = \text{blue}\} \end{align*} be the red and blue neighbourhoods of $x$. Then $\{N_r(x), N_b(x)\}$ partitions $V(K_n) \setminus \{x\}$, so \begin{align*} |N_r(x)| + |N_b(x)| = n - 1 = a + b - 1. \end{align*} [guided] For the inductive step we need a natural way to recurse into the smaller instances $R(s - 1, t)$ and $R(s, t - 1)$. The standard trick is to examine the colour-partitioned neighbourhoods of a single vertex. **Why $n = a + b$?** The pigeonhole principle on the partition $N_r(x) \cup N_b(x) = V(K_n) \setminus \{x\}$ gives $|N_r(x)| + |N_b(x)| = n - 1$. We want at least one of these neighbourhoods to be big enough to recursively apply Ramsey. If $n - 1 \geq a + b - 1$, i.e. $n \geq a + b$, then either $|N_r(x)| \geq a$ or $|N_b(x)| \geq b$: otherwise both would fall short, giving $(a - 1) + (b - 1) = a + b - 2 < a + b - 1$ total, contradiction. The minimal $n$ for which pigeonhole guarantees one of these is $n = a + b$. **Why the inductive hypothesis applies.** The pairs $(s - 1, t)$ and $(s, t - 1)$ both have $\min \geq 2$ (since $s, t \geq 3$), and both have coordinate sum $s + t - 1 < s + t$. So $a = R(s-1, t)$ and $b = R(s, t-1)$ exist by induction. [/guided] [/step] [step:Apply pigeonhole to split into the two inductive subcases] At least one of the following holds: \begin{align*} |N_r(x)| \geq a \qquad \text{or} \qquad |N_b(x)| \geq b, \end{align*} for otherwise $|N_r(x)| \leq a - 1$ and $|N_b(x)| \leq b - 1$, giving $|N_r(x)| + |N_b(x)| \leq a + b - 2 < a + b - 1$, contradicting the identity from the previous step. We handle the two cases separately; they are related by swapping the colours. **Case A: $|N_r(x)| \geq a = R(s - 1, t)$.** The restriction of $c$ to the complete graph on $N_r(x)$ is a 2-edge-colouring of $K_{|N_r(x)|}$. Since $|N_r(x)| \geq R(s-1, t)$, by the definition of $R(s - 1, t)$ this restriction contains either a red $K_{s-1}$ or a blue $K_t$. - If it contains a red $K_{s - 1}$ on some vertex set $W \subseteq N_r(x)$ with $|W| = s - 1$: every edge within $W$ is red, and every edge from $x$ to $W$ is red (since $W \subseteq N_r(x)$). Hence $W \cup \{x\}$ spans a red $K_s$. - If it contains a blue $K_t$: this is immediately a blue $K_t$ in the original colouring of $K_n$. Either way we find a red $K_s$ or a blue $K_t$. **Case B: $|N_b(x)| \geq b = R(s, t - 1)$.** Symmetrically, the restriction of $c$ to $N_b(x)$ is a 2-edge-colouring of $K_{|N_b(x)|}$ with $|N_b(x)| \geq R(s, t-1)$. By definition of $R(s, t-1)$, it contains a red $K_s$ or a blue $K_{t-1}$. - If a red $K_s$: done, this is a red $K_s$ in the original. - If a blue $K_{t-1}$ on $W \subseteq N_b(x)$ with $|W| = t - 1$: every edge within $W$ is blue, and every edge from $x$ to $W$ is blue. Hence $W \cup \{x\}$ spans a blue $K_t$. In every case we exhibit a red $K_s$ or a blue $K_t$ in the original colouring of $K_n$. Hence $R(s, t)$ exists and $R(s, t) \leq n = a + b = R(s - 1, t) + R(s, t - 1)$. The induction is complete. [guided] **Case A in detail.** Suppose $|N_r(x)| \geq a = R(s - 1, t)$. The key idea is that an edge inside $N_r(x)$ completes a red triangle with $x$ when combined with an $x$-to-$N_r(x)$ edge (which is red by definition). So if we can find a red $K_{s-1}$ inside $N_r(x)$, attaching $x$ upgrades it to a red $K_s$. Formally, restrict the colouring $c$ to the complete subgraph on $N_r(x)$. This is a 2-edge-colouring of a complete graph on at least $R(s-1, t)$ vertices, so by the definition of $R(s - 1, t)$ we get either a red $K_{s-1}$ or a blue $K_t$ inside $N_r(x)$. - *Red $K_{s-1}$ in $N_r(x)$:* let $W$ denote its vertex set, with $|W| = s - 1$. We claim $W \cup \{x\}$ is a red $K_s$. Every edge with both endpoints in $W$ is red by the case assumption. Every edge from $x$ to a vertex $v \in W \subseteq N_r(x)$ is also red, by definition of $N_r(x)$. The edge set of the complete graph on $W \cup \{x\}$ consists exactly of these two types, so every edge is red and $|W \cup \{x\}| = s$. - *Blue $K_t$ in $N_r(x)$:* this is already a blue $K_t$ in the host graph $K_n$ (subgraph of subgraph is subgraph), so we are done. **Case B** is identical with the roles of red/blue and $s/t$ swapped. Suppose $|N_b(x)| \geq b = R(s, t - 1)$. The restricted colouring on $N_b(x)$ contains either a red $K_s$ (done immediately) or a blue $K_{t-1}$; in the latter case its vertex set $W$ together with $x$ forms a blue $K_t$ (every edge in $W$ is blue, and every $x$-$W$ edge is blue since $W \subseteq N_b(x)$). **Pigeonhole is what makes this work.** At least one of $|N_r(x)| \geq a$ or $|N_b(x)| \geq b$ holds because otherwise both fail and $|N_r(x)| + |N_b(x)| \leq (a - 1) + (b - 1) = n - 2$, contradicting $|N_r(x)| + |N_b(x)| = n - 1$. **Conclusion of the induction.** In every case we produce the required monochromatic clique. Hence for $n = a + b$, every 2-colouring of $E(K_n)$ contains a red $K_s$ or blue $K_t$. By definition of the Ramsey number, $R(s, t)$ exists and $R(s, t) \leq n = R(s - 1, t) + R(s, t - 1)$. [/guided] [/step]