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

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