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

Материал из WikiGrapp
Версия от 17:01, 17 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''Лемма о рукопожатиях''' (''Handshake's lemma'') - ''Сумма степеней всех вершин графа ---...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

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

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

Литература

[Лекции]