Лемма о рукопожатиях: формула, доказательство и примеры

Лемма о рукопожатиях утверждает: сумма степеней всех вершин конечного неориентированного графа равна удвоенному числу его рёбер. Название напоминает о встрече людей: каждое рукопожатие учитывается дважды, по одному разу для каждого участника. Из формулы следует неожиданный факт: число вершин нечётной степени всегда чётно. Ниже докажем оба утверждения, научимся применять их в задачах и выясним, почему одной проверки суммы недостаточно для построения графа. В калькуляторе можно добавлять рёбра и наблюдать, как меняются степени.
Формулировка и смысл степени
Пусть - конечный неориентированный граф. Степень вершины равна числу концов рёбер, инцидентных этой вершине. В простом графе без петель и кратных рёбер это просто число её соседей. Изолированная вершина имеет степень ноль.
Лемма записывается так:
Здесь - число рёбер. Связность не требуется: в сумму входят вершины всех компонент, включая изолированные. Если представить вершины людьми, а рёбра взаимными рукопожатиями, то слева подсчитано общее число участий людей в рукопожатиях, справа - число рукопожатий, умноженное на два. Одно рукопожатие связывает двух участников, поэтому две величины совпадают.
Эта аналогия предполагает, что каждый человек может пожать руку другому не более одного раза, если речь идёт о простом графе. Для повторных рукопожатий нужны кратные рёбра; сама формула от этого не меняется.
Доказательство двойным подсчётом
Посчитаем пары «вершина - конец ребра» двумя способами. Если сначала выбрать вершину , таких пар для неё будет . Складывая по всем вершинам, получаем левую часть формулы.
Теперь сначала выберем ребро. У него два конца, и каждый даёт одну пару с соответствующей вершиной. Поэтому все рёбра вместе дают пар. Мы посчитали одно и то же множество двумя способами, значит, результаты равны. Здесь не приходится искать маршрут, раскраску или порядок обхода: достаточно аккуратно определить, что именно считаем.
Если у графа есть петля, оба её конца принадлежат одной вершине. Петля поэтому добавляет к степени этой вершины две, а не одну единицу; при таком соглашении доказательство остаётся верным. Кратные рёбра тоже считаются отдельно. В ориентированном графе отдельно определяют входящую и исходящую степени: сумма входящих равна числу дуг, как и сумма исходящих. Их общая сумма снова равна удвоенному числу дуг.
Пример: пять вершин и шесть рёбер
Возьмём вершины А, Б, В, Г, Д и рёбра АБ, АВ, АГ, БВ, ВГ, ГД. У вершины А три ребра, у Б два, у В три, у Г три, у Д одно. Следовательно,

Зная только список степеней этого графа, можно восстановить число рёбер: . Но нельзя однозначно восстановить, какие вершины соединены: один и тот же набор степеней может соответствовать разным графам. В калькуляторе выше сначала показан именно этот пример; если уменьшить число рёбер, удаляются последние рёбра заданного списка. Сравнивайте сумму столбцов с удвоенным числом рёбер при каждом положении ползунка.
Почему нечётных вершин чётное число
Разделим вершины на две группы по чётности степени. Сумма степеней всех вершин чётна, поскольку равна . Сумма чётных степеней тоже чётна, значит, сумма нечётных степеней должна быть чётной. А сумма нечётных целых чисел чётна тогда и только тогда, когда слагаемых чётное число.
Итак, число вершин нечётной степени всегда чётно, в том числе может равняться нулю. В нашем примере нечётные степени имеют А, В, Г и Д: таких вершин четыре. Значение степени при этом может быть разным; важно лишь, что каждая из четырёх степеней нечётна.
Это следствие удобно для быстрой проверки условия. Если в конечной сети объявлено ровно семь узлов с нечётным числом соединений, в описании или подсчёте ошибка. Однако чётность числа таких узлов ещё не гарантирует, что остальные данные согласованы между собой.
Как находить число рёбер и неизвестную степень
В задаче со списком степеней сначала сложите их, затем разделите сумму на два. Например, в графе десять вершин, и степень каждой равна трём. Тогда сумма степеней , а число рёбер равно . В общем случае для -регулярного графа с вершинами получаем . Отсюда сразу видно: если нечётно, то обязано быть чётным.
Если известны число рёбер и все степени, кроме одной, используйте ту же формулу как уравнение. Например, при шести рёбрах и известных степенях неизвестная степень равна . После вычисления проверьте ограничения конкретной задачи: в простом графе с пятью вершинами степень лежит от нуля до четырёх. При петлях или кратных рёбрах верхняя граница уже не действует.
Для полного простого графа каждая из вершин имеет степень , поэтому рёбер . Тот же результат получается как число способов выбрать пару различных вершин; различие между выбором пары и упорядочиванием рассмотрено в статье о сочетаниях и перестановках.
Достаточно ли чётной суммы степеней
Нет. Чётная сумма - необходимое, но не достаточное условие для последовательности степеней простого графа. Рассмотрим четыре числа : их сумма равна десяти, и число нечётных степеней равно четырём. Обе проверки пройдены, но построить такой простой граф нельзя.
Действительно, каждая вершина степени три должна соединяться со всеми тремя остальными вершинами. Таких вершин по условию три, поэтому четвёртая соединена со всеми ними и сама имеет степень три, а не один. Противоречие. Для полной проверки применяют, например, алгоритм Хавела - Хакими: степени упорядочивают, удаляют наибольшую и уменьшают соответствующее число следующих степеней, повторяя процедуру. Отрицательные значения или нехватка вершин означают невозможность; если все остатки нулевые, построение возможно.
Практический вывод: лемма помогает быстро отвергнуть некорректные данные, но не заменяет проверку всех ограничений. Особенно важно отличать простой граф от мультиграфа: то, что запрещено в одном классе, может быть разрешено в другом.
Где применяется лемма
В задаче о мостах Кёнигсберга степени районов помогают исследовать возможность пройти по каждому мосту один раз. Лемма гарантирует чётное число нечётных вершин, а критерий Эйлера дополнительно требует подходящей связности и нуля или двух нечётных вершин для соответствующего обхода. Одной чётности для маршрута недостаточно.
В компьютерной сети вершины могут представлять устройства, а рёбра - двусторонние соединения. Сумма числа подключений по устройствам должна быть вдвое больше числа соединений: это простая проверка данных инвентаризации. Но формула сама по себе не говорит, доступно ли одно устройство из другого. Для исследования достижимости нужен, например, обход графа в ширину.
В двудольном графе каждое ребро имеет по одному концу в каждой доле, поэтому сумма степеней отдельно по любой из двух долей равна . Эта форма полезна для моделей назначений и паросочетаний; их связь с покрытиями разбирает теорема Кёнига. А значение степени отдельной вершины и её роль в структуре графа подробнее обсуждаются в статье об эксцентриситете вершины.
Частые ошибки
- Считают каждое ребро один раз в сумме степеней. Его концы учитываются у обеих вершин, поэтому нужен множитель два.
- Записывают петлю как единицу степени. У неё два конца в одной вершине, и вклад равен двум.
- Считают ноль нечётным числом. Изолированная вершина имеет чётную степень ноль.
- Принимают чётную сумму за доказательство существования графа. Последовательность показывает, почему этого мало.
- Применяют формулу без уточнения направления. Для дуг отдельно считают входящие и исходящие степени.
FAQ
Работает ли лемма для несвязного графа?
Да. Каждое ребро по-прежнему имеет два конца, независимо от числа компонент; изолированные вершины добавляют к сумме ноль.
Может ли быть ровно одна вершина нечётной степени?
Нет, в конечном неориентированном графе число таких вершин всегда чётно. При удалении или добавлении обычного ребра чётность меняется сразу у двух его концов.
Можно ли по степеням восстановить граф?
Не всегда. Даже если последовательность реализуема, разные графы могут иметь одинаковые степени. Для восстановления нужны дополнительные сведения о соединениях.
Коротко
Лемма о рукопожатиях равна формуле : каждое ребро даёт два конца. Из неё следуют чётность числа нечётных вершин и способ найти число рёбер по степеням. Эти проверки необходимы, но сами по себе не устанавливают ни существование простого графа с заданными степенями, ни его связность.
Читайте также

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

Гиперграф: что это такое и как его построить
Гиперграф простыми словами: вершины, гиперрёбра и матрица инцидентности. Разбираем пример, степени вершин, связь с обычным графом и области применения.

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

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

Дерево: свойства и число рёбер
Как связаны вершины и рёбра дерева, почему их числа отличаются на единицу и какие признаки помогают отличить дерево от произвольного графа. Примеры и доказательство.

Теорема Форда-Фалкерсона о максимальном потоке
Теорема Форда-Фалкерсона связывает максимальный поток и минимальный разрез. Разбираем доказательство через остаточную сеть, пример и проверку решения.