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

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

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

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

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

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

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

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