Докажите, что R(3, 4) = 9. (R(3, 4) — наименьшее из тех чисел n, что в любом графе на n вершинах есть либо клика размера 3, либо независимое множество размера 4.)

Следствием доказательства теоремы Рамсея является неравенство: R(m, n) ≤ R(m − 1, n) + R(m, n − 1)
Однако при R(m − 1, n) и R(m, n − 1) – четных неравенство усиливается до: R(m, n) ≤ R(m − 1, n) + R(m, n − 1) − 1
Доказательство:
Рассмотрим 2–раскрашенный граф на k = R(m − 1, n) + R(m, n − 1) − 1 вершинах. Так как k –
нечетно, то найдется хотя бы одна вершина четной степени цвета 1, пусть это вершина v1.
Пусть вершина v1 соединена ребрами цвета 1 с вершинами из множества M и ребрами цвета 2
из множества N, причем |M| – четно. Аналогично доказательству теоремы Рамсея либо |M| ≥
R(m − 1, n) − 1, либо |N| ≥ R(m, n − 1). Но т.к. |M| – четно, а R(m − 1, n) − 1 – нечетно, то можно
усилить неравенство до |M| ≥ R(m − 1, n).

Предположим, что |M| ≥ R(m−1, n). Тогда либо подграф из вершин множества M содержит независимое множество размера n, что уже подходит для всего графа, либо клику размера m − 1, которая с вершиной v1 образует клику размера m Случай, когда |N| ≥ R(m, n − 1) аналогичен.
Получим, что при R(m − 1, n) и R(m, n − 1) – четных: R(m, n) ≤ R(m − 1, n) + R(m, n − 1) − 1
Тогда R(3, 3) ≤ R(3, 2) + R(2, 3) = 3 + 3 = 6, R(2, 4) = 4 ⇒ R(3, 4) ≤ R(3, 3) + R(2, 4) − 1 = 9
С другой стороны, R(3, 4) > 8, так как есть контрпример на 8 вершин:
Получим, что R(3, 4) > 8 и R(3, 4) ≤ 9 ⇒ R(3, 4) = 9