В любом графе сумма степеней всех вершин является четным числом.

Это утверждение - теорема о рукопожатиях, которая гласит, что сумма степеней всех вершин графа равна удвоенному числу ребер. Так как число ребер умножается на 2, то сумма степеней всегда будет четным числом.