Теорема Рамсея о полных графах утверждает, что в любой маркировке рёбер (цветами) достаточно большого полного графа можно найти монохроматические клики. 5

Формулировка теоремы:

Пусть даны натуральные числа n и m. 1 Тогда существует такое достаточно большое число N, что в любом полном графе на N вершинах (то есть все вершины соединены рёбрами), рёбра которого раскрашены в синий и красный цвета, найдётся подграф на n вершинах с рёбрами только красного цвета, либо найдётся подграф на m вершинах с рёбрами только синего цвета. 1

Минимальное такое число N называют числом Рамсея для n красных и m синих. 1