442
правки
Изменения
→Существование. Оценки сверху
===Существование. Оценки сверху===
{{Теорема|id=ter1|about=1
|statement=Пусть <tex>n,m \ge 2</tex> {{---}} натуральные числа. Тогда <tex>r(n,m) \le r(n,m-1)+r(n-1,m)</tex>. При этом если оба числа <tex>r(n,m-1)</tex> и <tex>r(n-1,m)</tex> {{---}} четные, то неравенство строгое.
|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> следует неравенство [[#ter1|из теоремы 1]].
