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

Рассмотрим граф, где вершины — ученики, а рёбра — знакомства. Степени вершин лежат от 68 до 101 — всего 34 возможных значения.

Предположим, что никакие четыре вершины не имеют одинаковой степени. Тогда каждое значение степени встречается не более трёх раз. Так как а учеников ровно 102, все степени от 68 до 101 должны встречаться ровно по 3 раза.

Нечётных степеней среди них

Значит, 17 нечетных значений, каждое встречается по 3 раза, следовательно, всего есть 51 вершина с нечётной степенью. Но в любом неориентированном графе число вершин нечётной степени — чётно. Противоречие.