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

Лемма о рукопожатиях (Handshake's lemma) — Сумма степеней всех вершин графа — четное число, равное удвоенному числу ребер.

Свое название лемма получила из-за следующей интерпретации: поскольку в каждом рукопожатии участвуют две руки, то при любом числе рукопожатий общее число пожатых рук (при этом каждая рука учитывается столько раз, во скольких рукопожатиях она участвовала) равно удвоенному числу рукопожатий. Лемма справедлива также для мульти- и псевдографов.

Литература

• Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.