Считаем рёбра

Рассмотрим граф, вершинами которого являются ученики, причём два ученика из разных отделений соединены красным ребром, если они знакомы, и синим — в противном случае. Пусть в трёх отделениях и учеников. Рассмотрим произвольных учеников из первых двух отделений. Пусть они знакомы. Тогда существует ровно треугольников в которых все ребра красные. Аналогично для незнакомых и найдутся ровно треугольников в которых все рёбра синие. Значит, общее число одноцветных треугольников равно Аналогично оно же равно и поэтому

Для трёх учеников из разных отделений, будем говорить, что и похожи для если соединен с и ребрами одного цвета. Для каждого ученика найдём количество пар, похожих для него, и подсчитаем сумму всех этих чисел двумя способами.

С одной стороны, каждая пара учеников из разных отделений является похожей ровно для учеников; всего таких пар следовательно, С другой стороны, в любом одноцветном треугольнике каждые два ученика похожи для третьего; если же треугольник разноцветный (скажем, ребро отличается по цвету от других), то в нём ровно одна пара похожа для третьего. Так как количество одноцветных треугольников равно а разноцветных — то Значит, откуда