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

На вечеринке каждый гость пожал кому-то руку. Сложите по всем гостям число пожатых рук — сумма обязательно выйдет чётной. Причина прозрачна: каждое рукопожатие считают двое. Переводим на язык графов: гости — вершины, рукопожатия — рёбра, и лемма о рукопожатии утверждает: сумма степеней всех вершин равна удвоенному числу рёбер. Факт восходит к Эйлеру и его задаче о кёнигсбергских мостах (1736) — с неё, по сути, началась вся теория графов.

Проверим на полном графе $K_4$: у каждой из четырёх вершин степень 3, сумма 12, рёбер 6 — сходится: $2\cdot 6=12$. Из чётности суммы вылетает главное следствие: число вершин нечётной степени чётно. В сумме нечётность могут создать только нечётные слагаемые — а их количество обязано быть чётным, иначе вся сумма была бы нечётной. Ответ «в компании трое пожали нечётное число рук» невозможен в принципе: такие данные можно забраковать, не считая ничего дальше.

Следствия, которые экономят время на контрольной. В любом графе с двумя и более вершинами найдутся две вершины одинаковой степени: если бы все степени были различны, это были бы ровно числа $0,1,\dots ,n-1$, но степени 0 и $n-1$ несовместимы — вершина, соединённая со всеми, исключает изолированную. Регулярный граф степени d на n вершинах содержит nd/2 рёбер — на этом держится формула числа рёбер полного графа. Для дерева на n вершинах сумма степеней равна $2(n-1)$, и отсюда выходят «у дерева минимум два листа» и другие любимые задачи семинаров.

Где лемма стреляет: эйлеровы циклы (критерий «все степени чётны» доказывается через неё), проверка подсчётов — если Σdeg вышла нечётной или не равна 2|E|, ошибка случилась раньше, чем вы её заметили; турнирные календари: сумма числа сыгранных матчей всегда чётна, ведь каждый матч играют двое. Базовые определения и примеры — в уроке графы: основы, эйлеровы маршруты и деревья разобраны в деревьях и алгоритмах, все формулы графов — в шпаргалке по графам и алгоритмам.