Пример $1.$

Рассмотрим набор точек, изображенных на иллюстрации. Для простоты восприятия проведем только красные отрезки.

Докажем, что синего треугольника не найдется. Для этого разделим точки на три уровня: точки $1,$ $2$ и $3$ будут принадлежать внешнему уровню, точки $4,$ $5$ и $6$ — среднему, а $7$ и $8$ — внутреннему. Заметим, что на каждом уровне все точки соединены между собой красными отрезками, а значит, если синий треугольник существует, все его вершины находятся на разных уровнях.

Вершина $7$ соединена со всеми вершинами среднего уровня, а значит, не может быть вершиной синего треугольника. Аналогично, вершина $5$ соединена со всеми вершинами внешнего уровня, а значит, не может быть вершиной синего треугольника. Тогда вершина $8$ соединена со всеми вершинами среднего уровня, кроме $5,$ и не может быть вершиной синего треугольника. Значит, ни одна вершина внутреннего уровня не является вершиной треугольника с синими сторонами, а значит, такого треугольника не найдется.

_________________________________________________________________________________________________________________________________________________________________________________

Пример $2.$

Возьмем два графа $K4$ с красными ребрами. Тогда синие отрезки образуют граф $K4,4,$ то есть двудольный граф, в котором могут быть только циклы четной длины, а треугольник — это цикл нечётной длины, следовательно треугольников нет.

_________________________________________________________________________________________________________________________________________________________________________________

Замечание. Если точек $9$ или более, то синий треугольник обязательно найдется. Другими словами, граф, дополнительный к планарному на $9$ и более вершинах, всегда содержит граф-треугольник в качестве подграфа.

Двудольные графы и переформулировки к ним