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

Это утверждение неверно. Сумма степеней всех вершин в графе всегда является чётным числом.