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

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

Таким образом, эйлеров граф может иметь либо две нечётные вершины, либо не иметь их совсем. 3