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

Неверно. В любом графе количество вершин нечётной степени всегда чётно. Это следует из того, что сумма степеней всех вершин графа равна удвоенному количеству рёбер, а значит, чётна. Если бы количество вершин нечётной степени было нечётным, то и сумма степеней была бы нечётной, что противоречит утверждению о том, что сумма степеней равна $$2|E|$$.