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

Это утверждение верно. Количество вершин с нечётной степенью всегда чётное число. Это следует из того, что сумма всех степеней вершин равна удвоенному числу ребер.