Изменения
→Экстремальные примеры и оценки снизу
|statement=Для любого натурального числа <tex>k \ge 2</tex> выполняется неравенство <tex>r(k,k) \ge k^{k/2}</tex>
|proof=
Так как <tex>Rr(2,2)=2</tex>, достаточно рассмотреть случай <tex>k \ge 3</tex>.
Зафиксируем множество различных помеченных вершин <tex>v_i,...,v_n</tex>. Пусть <tex>g(n,k)</tex> — деля среди всех графов на вершинах <tex>v_i,...,v_n</tex> тех графов, что содержат клику на <tex>k</tex> вершинах. Всего графов на наших вершинах, очевидно <tex>2^{C^2_n}</tex> (каждое из возможных <tex>C^2_n</tex> можно провести или не провести).
