Числа Рамсея

Нам надо показать, что в любом графе на вершине, ребра которого покрашены в два цвета можно найти либо первого цвета, либо второго цвета. Предположим, что не найдется полного подграфа на вершинах второго цвета. Выделим максимальный полный подграф второго цвета. Присвоим ему номер В ем не больше вершины по нашему предположению. Заметим, что из каждой из оставшихся вершин в наш подграф ведет хотя бы одно ребро первого цвета (иначе мы бы выбрали не максимальный полный подграф). Далее среди оставшихся вершин снова выберем максимальный полный подграф второго цвета, присвоим ему номер и так далее. На каждом шаге мы выкидываем не более вершин, поэтому мы сможем выделить минимум подграфов, то есть минимум полных подграфов. Нам буду нужны первые выбранных подграфов, которые мы занумеровали числами от до Рассмотрим дерево Подвесим его за вершину. Все вершины дерева разбились на уровни. Вершину, за которую подвесили пронумеруем 1. Далее нумеруем по возрастанию все вершины первого уровня, потом второго и так далее.

Теперь будем строить наше дерево, причем -ую вершину дерева будем искать в -ом полном подграфе. На -ом шаге мы будем добавлять к графу вершину с номером Изначально выберем любую вершину из первого подграфа. Когда нам нужно добавить вершину с номером мы смотрим на номер ее предка. Он имеет меньший номер а значит, уже выбран в -ом подграфе. Но тогда из этой вершины должно вести ребро первого цвета в -ый подграф, конец этого ребра и будет нашей вершиной с номером добавим его в дерево. Таким образом, мы смогли построить