Ramsey number: why is R(s, t)=R(t, s)?

Question

So let's assume that $s \leq t$, and we use the following definition: the Ramsey number $R(s, t)$ is the smallest value of $N$ such that under every red-blue coloring of $K_{N}$, there is a red $K_s$ or a blue $K_t$.

All graph theory books and lecture notes I can find say that "it is obvious that $R(s, t) = R(t, s)$", but unfortunately I can't see this.

So let's say $R(s, t) = N$, and under a certain red-blue coloring of $K_N$, we have a blue $K_t$, then clearly we have a red $K_s$ since $s \leq t$. However, if we have another red-blue coloring of $K_N$ that only yields a red $K_s$ but no blue $K_t$, then how can we assure that we can certainly obtain a red $K_t$ or a blue $K_s$?

I appreciate any help.

Answer 1

Fix a red-blue colouring of $K_N$ and construct a new colouring by exchanging the colour red with the colour blue. This new colouring either contains a red $K_s$ or a blue $K_t$ by definition of $N$. Hence the original colouring contains a red $K_t$ or a blue $K_s$ as required.

Answer 2

Fix a red-blue colouring $c$ of $K_N$ where $N=R(s,t)$.

So $c$ is a map from $E_N$ (the edges of $K_N$, i.e. all unordered pairs $\{i,j\}$ where $i \neq j \in \{1,\ldots, N\} = V_N$, the vertices of $K_N$) to $\{r,b\}$, the set of "colours". The "swap map" on the colours can be defined as $s: \{r,b\}\to \{r,b\}$ with $s(r) = b, s(b)= r$.

Define $c': E_N \to \{r,b\}$ by $c'(\{i,j\}) = s(c(\{i,j\}))$, and this is another colouring of $K_N$. By definition of $R(s,t)$ there is either a red $K_s$ or a blue $K_t$ for $c'$. A red $K_s$ is just a subset $A \subset V_N$ such that $|A| = s$ and $\forall i\neq j \in S: c'(\{i,j\}) = r$, and as $c'(\{i,j\})=r$ iff $C(\{i,j\})=b$, we in fact have a blue $K_s$ for $c$, or (similarly) a red $K_t$ for $c$ (when we have a blue $K_t$ for $c'$).

So in summary of the previous paragraphs: any red-blue colouring of $K_N$ has a red $K_t$ or blue $K_s$. As $R(t,s)$ is the minimal number of vertices that this holds for, we have $R(t,s) \le N= R(s,t)$.

Now the same argument starting with $N= R(t,s)$ will give $R(s,t) \le R(t,s)$ and we're done.