Какие математические задачи связаны с леммой о рукопожатиях?

Некоторые математические задачи, связанные с леммой о рукопожатиях:

• Задача о количестве рукопожатий в компании. 1 В компании 15 человек, каждый сделал по 5 рукопожатий. 1 Нужно найти общее количество рукопожатий. 1 Решение: рассмотрим граф, в котором люди — вершины, а сделанные рукопожатия — рёбра. 1 Тогда суммарная степень всех вершин равна 15⋅5=75. 1 По теореме эта сумма должна быть в два раза больше числа рёбер. 1 Но сумма нечётна, и такое невозможно, ведь количество рёбер не может быть нецелым. 1
• Задача о вассалах короля. 4 У короля 19 баронов-вассалов. 4 Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств? 4 Решение базируется на том факте, что при построении графа, соответствующего условиям задачи, получается противоречие со следствием леммы о рукопожатиях о чётном количестве нечётных вершин графа. 4
• Задача о 9 отрезках на плоскости. 4 Нужно определить, можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими. 4 Решение также включает использование следствия леммы о рукопожатиях. 4