Доказательство индукцией по $r+s$. База: $R(r,2)=r$ (синяя $K_{2}$ — одно ребро; если нет синего ребра, граф полный красный $K_{r}$ при $N=r$). Шаг: $R(r,s) \leq R(r-1,s)+R(r,s-1)$. Пусть $N = R(r-1,s)+R(r,s-1)$. Зафиксируем вершину $v$: из неё $N-1$ рёбер. По принципу Дирихле хотя бы $R(r-1,s)$ красных или $R(r,s-1)$ синих. В первом случае среди красных соседей (их $\geq R(r-1,s)$) по индукции есть красный $K_{r-1}$ или синий $K_{s}$; красный $K_{r-1}$ вместе с $v$ — красный $K_{r}$. Аналогично второй случай. Граница: $R(r,s) \leq R(r-1,s)+R(r,s-1) \leq \binom{r+s-3}{r-2}+\binom{r+s-3}{r-1} = \binom{r+s-2}{r-1}$ по тождеству Паскаля.

💡 Авторизуйтесь, чтобы получить помощь AI-тьютора с подсказками и решениями!