В чем заключается теорема о рукопожатиях в графах?

Теорема о рукопожатиях в графах заключается в том, что сумма степеней всех вершин графа (или мультиграфа без петель) — чётное число, равное удвоенному числу рёбер. 5

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

Следствие из теоремы: в любом графе число вершин нечётной степени чётно. 24

Аналогом теоремы о рукопожатиях для ориентированного графа является утверждение, что сумма входящих и исходящих степеней всех вершин ориентированного графа — чётное число, равное удвоенному числу рёбер. 5