Таблицы Брадиса

Из этого будет следовать, что

Из этого будет следовать, что

Элементы математики в задачах - Г. А. Мерзон

і = 1,..., п — 1. Если (п + 1)-я команда выиграла у всех остальных, ей можно присвоить номер п + 1. Иначе, (п + 1)-ю команду можно вставить в список сразу перед командой с наименьшим номером среди тех, кому она проиграла.

Задача 19* (теорема Рамсея). а) Докажите, что для произвольных натуральных т, п существует натуральное к такое, что в произволь­ном графе с к вершинами найдется либо т попарно соединенных ребрами вершин, либо п попарно несоединенных. Наименьшее такое к обозначается Я(т, п). б) Найдите Л(3,4).

142                                    Теория графов 1

Решение. а) Докажем индукцией по т + п, что если Я(т — 1, п) и Я(т, п — 1) существуют, то в любом графе с числом вершин, не меньшим чем Я(т — 1, п) + Я(т, п — 1), найдется либо т попарно соединенных ребрами вершин, либо п попарно несоединенных. Из этого будет следовать, что Я(т, п) существует для всех т, п и Я(т, п) ^ ^ Я(т — 1, п) + Я(т, п — 1).

Рассмотрим какую-нибудь вершину V в произвольном графе с не менее чем Я(т — 1, п) + Я(т, п — 1) вершинами. Эта вершина либо соединена ребром хотя бы с Я(т — 1, п) вершинами, либо не соедине­на ребром хотя бы с Я(т, п — 1) вершинами. В первом случае среди вершин, соединенных с V, найдется либо т — 1 попарно соединенных (тогда они вместе с V образуют т попарно соединенных вершин), либо п попарно не соединенных. Во втором случае среди вершин, не соединенных с V, найдется либо т попарно соединенных, либо п — 1 попарно не соединенная (которые вместе с V образуют п по­парно соединенных). Итак, в любом случае найдется либо т попарно соединенных вершин, либо п попарно не соединенных.

б)  В силу предыдущего пункта Я(3, 4) ^ Л(2, 4) + Л(3, 3). Заметим, что Я(2, п) = п для любого п. Кроме того, по задаче 4 Л(3, 3) = 6. Следовательно, Я(3, 4) ^ 4 + 6 = 10. Допустим, существует граф из 9 вершин, не содержащий ни трех попарно соединенных, ни четырех попарно несоединенных вершин. В предыдущем пункте было дока­зано, что степень каждой вершины меньше Я(2, 4) = 4, и вершина не может быть не соединена с какими-то Я(3, 3) = 6 другими. Следо­вательно, степень каждой вершины меньше 4 и больше 8 — 6 = 2, а значит, равна 3. Следовательно, сумма степеней всех вершин равна