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

Лемма о рукопожатиях (теорема) гласит, что в любом графе сумма степеней всех вершин равна удвоенному числу рёбер. 13

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

• Задача о соединении телефонов. 1 Нужно определить, можно ли соединить 15 телефонов проводами так, чтобы каждый был соединён ровно с пятью другими. 1 Для решения строят граф, где вершины соответствуют телефонам, а рёбра — соединяющим их проводам. 1 Затем подсчитывают количество рёбер, учитывая, что каждое из них учтено дважды (соединяет две вершины). 1 Если полученное число нецелое, то такого графа не существует, а значит, и соединить телефоны требуемым образом невозможно. 1
• Задача о вассалах короля. 4 Нужно определить, может ли оказаться так, что у каждого вассального баронства 1, 5 или 9 соседних баронств. 4 Решение базируется на том, что при построении графа, соответствующего условиям задачи, получают противоречие со следствием леммы о рукопожатиях о чётном количестве нечётных вершин графа. 4
• Задача о 9 отрезках на плоскости. 4 Нужно определить, можно ли нарисовать на плоскости 9 отрезков так, чтобы каждый пересекался ровно с тремя другими. 4 Для решения строят граф, где вершинами будут отрезки. 4 Две вершины соединяют ребром только в том случае, если соответствующие отрезки пересекаются, то есть степень каждой вершины по условию задачи должна равняться 3. 4

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