Так, ну сейчас надо будет опять, как уже в случае R(3, 3) у нас с вами было, рассматривать какие-то альтернативы. Давайте постараемся делать это достаточно тоже подробно и медленно, дабы слушатели не отрубились, если им такая штука не была еще привычна ранее. Но, повторяю, рассуждение очень похоже на однажды проделанное. Так. Давайте прежде всего введем обозначение n равняется вот этой величине R(s − 1, t) + R(s, t − 1). Введем вот такое вот обозначение. И наша цель — показать, давайте напишу: цель — показать, что R(s, t) не превосходит вот этого числа n. В свою очередь, что это означает? Еще раз давайте вспомним определение. Что означает что R(s, t) не превосходит n? Это означает, в свою очередь, что для любого графа на n вершинах либо в этом графе есть полный подграф на s вершинах, давайте я его покороче обозначу, стандартно, Ks, либо в нем, вот в этом графе, есть Ks, либо в этом графе есть независимое множество на t вершинах. Вот. Это цель. Вот я ее так прямо выделю, чтобы было совершенно понятно — вот именно это мы хотим доказать. Мы ввели обозначение n, и теперь хотим взять совершенно произвольный граф на n вершинах и продемонстрировать, что либо в нем есть Ks, либо в его дополнении есть Kt. Ну то есть в нем самом есть независимое множество на t вершинах, а в дополнении, стало быть, есть полный граф на t вершинах. Так. Ну хорошо, давайте зафиксируем произвольный граф на n вершинах и будем доказывать то, что хотим. Зафиксируем произвольный граф на n вершинах. Помните, как у нас было? Мы раньше фиксировали произвольный граф на шести вершинах и доказывали, что либо в нем есть треугольник, либо в нем есть треугольник из отсутствующих ребер. Либо в нем есть треугольник из его ребер, либо в нем есть треугольник из тех ребер, которых в нем нет. Ну вот теперь у нас произвольный граф уже не на шести, а на вот стольких вершинах, но рисунок будет таким же. Мы выделим первую вершину, которую, как водится, обзовем А₁, ну а дальше там пойдут какие-то потенциальные соседки: А₂, А₃, ..., An. Всех уж перечислить не могу, потому что их больше не шесть, а какое-то там страшное количество, вообще говоря. Вот. Теперь вспоминаем еще раз то рассуждение, которое нас привело к успеху в случае с шестеркой. Мы говорили так: по принципу Дирихле либо здесь есть 3 соседки, либо здесь есть 3 несоседки, антисоседки то есть. Три подружки, которые подружками не являются, то есть для данной вершины соседками не являются. Либо 3, либо 3. Ну почему? Потому что их всего было 5 вот здесь вот. А теперь у нас их всего n − 1. Поэтому альтернатива тоже меняется. Я утверждаю, что либо у А₁ есть хотя бы R(s − 1, t) соседей, ну то есть вершин, смежных с ней в графе... Соседей среди оставшихся вершин А₂, ..., An, либо у нее есть хотя бы (ну то есть не менее) R(s, t − 1) несоседей. Либо столько соседей, ну либо не посчастливилось, столько несоседей. Вот в точности, как это было для случая R(3, 3). Давайте я еще, окончательно поясню, чтобы было понятно. Смотрите: почему именно такая альтернатива? Почему либо столько, либо столько? Ну давайте предположим, что и здесь на самом деле меньше, и здесь на самом деле меньше. Вот предположим такую неприятность, горе случилось. Не прав я, обманул вас, нельзя утверждать, что либо хотя бы столько, либо хотя бы столько. Вот нельзя, обманул. Но тогда что это значит, еще раз? Меньше, чем столько хотя бы неверно? Меньше, чем R(s−1, t) — это означает, утверждение «меньше» — оно равносильно тому, что ≤ (R (s − 1, t) − 1), потому что, ну как, количество соседей — это целое число. Если мы не можем утверждать, что их хотя бы столько, а можем лишь утверждать, что их строго меньше, чем столько — ну тогда это, конечно, для целых чисел равносильно тому, что их не больше, чем столько минус один. Это очень важное наблюдение. И здесь то же самое. Если мы предполагаем, что я ошибся, и тоже нельзя утверждать, что хотя бы столько, тогда не больше, (вот здесь вот давайте я стрелку напишу) в случае противного давайте напишем ≤ R (s, t − 1) − 1 Но если и здесь ≤ R (s − 1, t) − 1 и здесь ≤ R (s, t − 1) − 1, то в сумме, смотрите, не больше, чем это плюс это минус 1 минус 1, то есть минус 2. Но это плюс это — это ведь, по определению, n. Получается ≤ n − 2. Но у нас вот здесь, среди A₂, ..., An n − 1 вершина. Как же так может быть, что и соседей, и несоседей вместе не больше, чем n − 2? Так никак не может быть. Их всего n − 1 потенциальных соседей и несоседей. Противоречие. И значит, я вас не обманул. Значит, действительно либо А₁ хотя бы со столькими соединена, либо, если уж этого не случилось, хотя бы со столькими она не соединена.