Какие задачи в теории графов решаются с помощью теоремы о рукопожатиях?

С помощью леммы о рукопожатиях в теории графов решаются, например, следующие задачи:

• Задача о вассалах короля. urok.1sept.ru У короля 19 баронов-вассалов. urok.1sept.ru Может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств? urok.1sept.ru Решение базируется на том, что при построении графа, соответствующего условиям задачи, получается противоречие со следствием леммы о рукопожатиях о чётном количестве нечётных вершин графа. urok.1sept.ru
• Задача о 9 отрезках на плоскости. urok.1sept.ru Можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими? urok.1sept.ru
• Задача о 30 людях в классе. foxford.ru Может ли быть так, что 9 из них имеют по 3 друга (в этом классе), 11 — по 4 друга, а 10 — по 5 друзей (считается, что все дружбы взаимные)? foxford.ru Решение базируется на том, что если бы это было возможно, то можно было бы нарисовать граф с 30 вершинами, 9 из которых имели бы степень 3, 11 — степень 4, 10 — степень 5. foxford.ru Однако у такого графа 19 нечётных вершин, что противоречит следствию из леммы о рукопожатиях. foxford.ru