299
правок
Изменения
→Существование. Оценки сверху
|proof=
1) Рассмотрим граф на <tex>r(n, m — 1) + r(n — 1, m)</tex> вершинах с рёбрами цветов 1 и 2 и ее произвольную вершину <tex>a</tex>. Тогда либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n, m — 1)</tex> рёбер цвета 2, либо от вершины <tex>a</tex> отходит хотя бы <tex>r(n—1, m)</tex> рёбер цвета 1. Случаи аналогичны, рассмотрим первый случай и граф на <tex>r(n, m — 1)</tex> вершинах, соединенных с <tex>a</tex> рёбрами цвета 2. На этих вершинах есть либо граф на <tex>n</tex> вершинах с ребрами цвета 1, либо граф на <tex>m—1</tex> вершинах с рёбрами цвета 2. Во втором случае добавим вершину <tex>a</tex> и получим граф на <tex>m</tex> вершинах с рёбрами цвета 2. Теперь из определения <tex>r(n, m)</tex> следует [[#t1|неравенство]].
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>а </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>r(n, m) < r(n, m— 1) + r(n — 1, m) — 1</tex>.
}}
