442
правки
Изменения
→Существование. Оценки сверху
|proof=
<tex>1)</tex> Докажем с помощью метода математической индукции по <tex>rn+sm</tex>.
'''База:''' <tex>R(n,\;1) = R(1,\;n) = 1</tex>, так как 1-вершинный граф можно считать полным графом любого цвета.
'''Индукционный переход:'''. Пусть <tex>rn>1</tex> и <tex>sm>1</tex>. Рассмотрим полный чёрно-белый граф из <tex>R(rn-1,\;sm)+R(rn,\;sm-1)</tex> вершин. Возьмём произвольную вершину <tex>v</tex> и обозначим через <tex>M</tex> и <tex>N</tex> множества инцидентные <tex>v</tex> в чёрном и белом подграфе соответственно. Так как в графе <tex>R(rn-1,\;sm)+R(rn,\;sm-1)=|M|+|N|+1</tex> вершин, согласно принципу Дирихле, либо <tex>|M|\geqslant R(rn-1,\;sm)</tex>, либо <tex>|N|\geqslant R(rn,\;sm-1)</tex>.
Пусть <tex>|M|\geqslant R(rn-1,\;sm)</tex>. Тогда либо в <tex>M</tex> (и следовательно во всём графе) есть белый <tex>K_sK_m</tex>, что завершает доказательство, либо в <tex>M</tex> есть чёрный <tex>K_{rn-1}</tex>, который вместе с <tex>v</tex> образует чёрный <tex>K_rK_n</tex>. Случай <tex>|N|\geqslant R(rn,\;sm-1)</tex> рассматривается аналогично.
2) Рассмотрим клику на <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>.
}}
