Изменения

'''База:''' <tex>Rr(n,\;1) = Rr(1,\;n) = 1</tex>, так как 1-вершинный граф можно считать полным графом любого цвета.

'''Индукционный переход:'''. Пусть <tex>n>1</tex> и <tex>m>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>Rr(n-1,\;m)+Rr(n,\;m-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>Rr(n-1,\;m)+Rr(n,\;m-1)=|M|+|N|+1</tex> вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant Rr(n-1,\;m)</tex>, либо <tex>|N|\geqslant Rr(n,\;m-1)</tex>.

Пусть <tex>|M|\geqslant Rr(n-1,\;m)</tex>. Тогда либо в <tex>M</tex> (и следовательно во всём графе) есть белый <tex>K_m</tex>, что завершает доказательство, либо в <tex>M</tex> есть чёрный <tex>K_{n-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_n</tex>. Случай <tex>|N|\geqslant Rr(n,\;m-1)</tex> рассматривается аналогично.<tex>2) </tex> Рассмотрим клику на <tex>r(n, m-l)+r(n-1, m)-1</tex> вершинах с рёбрами цветов 1 и 2 и его произвольную вершину <tex>a</tex>. Если вершине <tex>a</tex> инцидентны хотя бы <tex>r(n,m-1)</tex> рёбер цвета 2 или хотя бы <tex>r(n-1,m)</tex> рёбер цвета 1, то мы найдём в графе клику на <tex>n</tex> вершинах с рёбрами цвета 1 или клику на <tex>m</tex> вершинах с рёбрами цвета 2. Остаётся лишь случай, когда вершине <tex>a</tex> инцидентны ровно <tex>r(n, m-1)-1</tex> рёбер цвета 2, то же самое для всех остальных вершин. Это означает, что в графе из рёбер цвета 2 всего <tex>r(n, m-1)+r(n-1, m)-1</tex> вершин и степень каждой вершины равна <tex>r(n, m-1)-1</tex>. Однако, тогда в графе нечётное количество вершин нечётной степени. Противоречие показывает нам, что в случае, когда <tex>r(n, m-1)</tex> и <tex>r(n-1,m)</tex> — чётные, выполняется неравенство <tex>(n, m)<r(n, m-1)+r(n-1, m)-1</tex>.