Сумма степеней всех вершин графа всегда чётна, потому что она равна удвоенному числу рёбер графа. 25

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

Степень вершины графа — это количество рёбер, исходящих из этой вершины. 1 Каждое ребро прибавляет единицу к степени каждой из двух вершин, которые оно соединяет. 2