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

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

Неориентированный граф

Лемма:

Сумма степеней всех вершин графа (или мультиграфа без петель) — четное число, равное удвоенному числу ребер: [math] \sum\limits_{v\in V(G)} deg\ v=2 |E(G)|[/math]

Доказательство:

[math]\triangleright[/math]

Возьмем пустой граф. Сумма степеней вершин такого графа равна нулю. При добавлении ребра, связывающего любые две вершины, сумма всех степеней увеличивается на 2 единицы. Таким образом, сумма всех степеней вершин четна и равна удвоенному числу ребер.

[math]\triangleleft[/math]

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

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

Ориентированный граф

Лемма:

Сумма входящих и исходящих степеней всех вершин ориентированного графа — четное число, равное удвоенному числу ребер: [math]\sum\limits_{v\in V(G)} deg^{-}\ v \; + \sum\limits_{v\in V(G)} deg^{+}\ v=2 |E(G)| [/math]

Доказательство:

[math]\triangleright[/math]

Аналогично доказательству леммы о рукопожатиях неориентированном графе.

[math]\triangleleft[/math]

Источники

• Lecture Notes on Graph Theory By Tero Harju, Department of Mathematics University of Turku, 2011 — с. 7-8
• Handshaking lemma — Wikipedia