442
правки
Изменения
→Числа Рамсея
Чтобы получить лучшее представление природы чисел Рамсея, приведем пример. Докажем, что <tex>r(3,3) = 6</tex>.
Представим, что ребра <tex>K_6</tex> раскрашены в два цвета: красный и синий. Возьмем вершину <tex>v</tex>. Данной вершине, как и всем другим, инцидентны 5 ребер, тогда согласно принципу Дирихле хотя бы три из них одного цвета. Для определенности положим, что хотя бы 3 ребра, соединяющие вершину <tex>v</tex> с вершинами <tex>r</tex> , <tex>s</tex> <tex>t</tex>, синие. Если хотя бы одно из ребер <tex>rs</tex>, <tex>rt</tex>, <tex>st</tex>, то есть синий треугольник (полный граф на трёх вершинах), иначе, если они все красные, то есть красный треугольник. Таким образом, <tex>r(3,3) \le 6 </tex>.Чтобы доказать, что <tex>r(3,3) = 6 </tex>, предъявим такую раскраску графа <tex>K_5</tex>, где нет клики на трех вершинах ни синего, ни красного цвета. Такая раскраска представлена на рисунке.
===Теорема Рамсея. Оценки сверху===
