Лемма о рукопожатиях

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