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

Материал из Викиконспекты
Версия от 01:51, 1 октября 2010; 192.168.0.2 (обсуждение) (Рустам, что со склонением прилагательных?)
Перейти к: навигация, поиск

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

Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер:

[math]\Sigma_{v\in V(G)}deg v=2 |E(G)|[/math]

Следствие 1 В любом графе число вершин нечетной степени четно

Следствие 2 Число ребер в полном графе [math]\frac{n(n-1)}{2} [/math]