Для решения этой задачи воспользуемся теорией Рамсея.

По теореме Рамсея об однородных графах, для любого натурального числа n находимое наименьшее число точек, при котором гарантированно можно найти монотонный подграф заданного порядка, равно 6.

Итак, докажем, что при n = 5 не всегда можно найти треугольник с одноцветными сторонами. Предположим, что каждая точка соединена с четырьмя другими (так как никакие три точки изначально не лежат на одной прямой). Также предположим, что в том числе в этом случае нет монотонного подграфа на 6 точках. Тогда у каждой точки есть ровно по два соседа каждого цвета.

Рассмотрим точку A. Она соединена с четырьмя другими точками: B, C, D и E. Поскольку у A есть по два соседа каждого цвета, например, B и C – красного цвета, D и E – зеленого цвета (если у них нет общего цвета, то мы нашли искомый подграф на 6 вершинах), то отрезок BC должен быть синего цвета. Рассмотрим точку B. Она соединена с точками A, C, D и E. По тем же самым причинам, она имеет двух «красных» и двух «зеленых» соседей, и, следовательно, отрезок CD синего цвета. Однако это приводит к тому, что треугольник ACB является равноцветным треугольником.

Таким образом, при n = 5 нельзя гарантированно найти треугольник с одноцветными сторонами. Следовательно, для гарантированного нахождения треугольника с одноцветными сторонами необходимо n >= 6 точек.