В эйлеровом графе не может быть вершин нечётной степени, потому что для существования эйлерова цикла необходимо и достаточно, чтобы степени всех его вершин были чётными. 13

Это следует из того, что при движении по эйлеровому циклу подсчитываются степени вершин: так как все рёбра в цикле различны, прохождение каждой вершины добавляет 2 в степень этой вершины. 1 Так как в цикл входят все рёбра, то когда обход будет закончен, будут определены степени всех вершин, которые будут чётными. 1

Также в любом графе число вершин нечётной степени должно быть чётным, что следует из леммы о рукопожатиях и теоремы Эйлера: сумма степеней вершин графа равна удвоенному количеству рёбер, то есть чётному числу. 13