Допустим есть граф с $$$n$$$ вершинами и $$$m$$$ рёбрами, и мы хотим найти три вершины $$$a$$$, $$$b$$$, $$$c$$$ такие, что есть рёбра $$$a-b$$$ и $$$b-c$$$, но нет ребра $$$a-c$$$. Напишем функцию check(b), которая находит такую тройку для заданной вершины $$$b$$$.

check(b)
    for(a: соседи b)
        for(c: соседи b)
            if(a и c не смежны)
                ответ: a, b, c
                exit()

Вызовем check от вершины с самым большим количеством соседей — пусть это количество равно $$$k$$$. Тогда эта функция отработает за $$$O(min(k^2,m))$$$, поскольку каждый цикл проходится по $$$k$$$ вершинам, но с другой стороны условие a и c не смежны не может более $$$m$$$ раз вернуть false, так как всего есть $$$m$$$ рёбер.

Итак, если мы получили ответ, то всё хорошо, алгоритм отработал не больше, чем за $$$O(n+m)$$$. Иначе все $$$k$$$ соседей вершины $$$b$$$ связаны между собой и связаны с вершиной $$$b$$$. Следовательно их степень $$$\ge (k-1)+1=k$$$. Но ведь начальная вершина $$$b$$$ имеет наибольшую степень — $$$k$$$. Значит все рассмотренные вершины связаны только друг с другом, и больше ни с кем. Понятно, что из них никак не составить "почти треугольник". Поэтому забудем про все эти $$$k+1$$$ вершину и начнём алгоритм заново без этих вершин. Повторяя так много раз, алгоритм либо найдёт нужную тройку вершин, либо удалит все вершины и скажет, что искомой тройки не существует.