= Solution
The <diagonal Ramsey number> $R(s)$ is the least <positive integer> $N$ such that every red-blue <edge colouring> of the <complete graph> $K_N$ contains a <monochromatic> copy of $K_s$.
For the existence and bound, write $R(r,s)$ for the least $N$ forcing either a red $K_r$ or a blue $K_s$. Given a vertex $v$ of $K_{R(r-1,s)+R(r,s-1)}$, the <pigeonhole principle> says that at least $R(r-1,s)$ incident edges are red or at least $R(r,s-1)$ are blue. In the first case those red neighbours contain a red $K_{r-1}$, which joins to $v$ to make a red $K_r$, or a blue $K_s$; the second case is symmetric. Hence
$$
R(r,s)\leq R(r-1,s)+R(r,s-1).
$$
Starting from $R(1,s)=R(r,1)=1$ and using <Pascal's identity> gives the <binomial upper bound for a Ramsey number>
$$
R(r,s)\leq\binom{r+s-2}{r-1}.
$$
Therefore
$$
R(s)\leq\binom{2s-2}{s-1}<\sum_{j=0}^{2s-2}\binom{2s-2}{j}=2^{2s-2}<4^s,
$$
which proves both existence and the required estimate.
To determine $R(3)$, color a <cycle graph> $C_5$ red and its <complement graph>, also a $C_5$, yellow. This colors $K_5$ without a monochromatic triangle, so $R(3)>5$. At any vertex of a red-yellow $K_6$, at least three of the five incident edges have one color. If an edge among their three other endpoints has that color, it completes a monochromatic triangle with the chosen vertex; if none does, those three endpoints themselves form a triangle of the other color. Thus $R(3)\leq6$, and
$$
\boxed{R(3)=6}.
$$
The same local argument proves uniqueness on $K_5$. No vertex can have three incident edges of one color: their other endpoints would either contain an edge of that color or form a triangle of the other color. Every vertex therefore has <vertex degree> at most two in each color, and because the two degrees sum to four, each is exactly two. Each color class is consequently a <regular graph> of degree two on five vertices, hence a single $C_5$. Up to relabelling, the coloring is exactly the cycle-and-complement coloring above.
Finally, the <monochromatic-triangle counting formula> gives, for a coloring of $K_6$ with red degrees $d_v$,
$$
M=\binom63-\frac12\sum_vd_v(5-d_v)
\geq20-\frac12(6\cdot6)=2.
$$
The bound is attained by coloring all edges of $K_{3,3}$ red and the two complementary copies of $K_3$ yellow: there are no red triangles and exactly two yellow triangles. The least requested number is therefore
$$
\boxed{n=2}.
$$
Back to article page
