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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
Версия для печати больше не поддерживается и может содержать ошибки обработки. Обновите закладки браузера и используйте вместо этого функцию печати браузера по умолчанию.

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

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

Литература

  • Лекции по теории графов / В.А.Емеличев, О.И.Мельников, В.И.Сарванов, Р.И.Тышкевич. — М.: Наука, 1990.
Источник — http://pco.iis.nsk.su/grapp/index.php?title=Лемма_о_рукопожатиях&oldid=7277