Числа Рамсея

Докажем, что в графе, в котором нет полного подграфа первого цвета на вершинах и полного подграфа второго цвета на вершинах, не более ребер. Будем вести индукцию по Базу проверим для Рассмотрим произвольную вершину Заметим, что из нее выходит не более ребер первого цвета, так как иначе среди таких вершин можно было бы выбрать либо второго цвета, либо первого цвета, а затем, добавив к нему получить первого цвета. Аналогично из выходит не более ребер второго цвета. Тогда всего вершин не больше, чем

Таким образом, переход доказан.