Может ли в графе существовать эйлеров путь, если в этом графе 2 вершины чётной степени и 4 вершин

[Klug]

Как подойти к выполнению задания 7 класса: - может ли в графе существовать эйлеров путь, если в этом графе 2 вершины чётной степени и 4 вершины нечётной степени?

 

[Fuchs]

Нет, не может существовать. Эйлеров путь (проходящий через каждое ребро ровно один раз) существует, когда в графе 0 либо 2 вершины нечетной степени. В данном случае у нас 4 вершины нечетной степени, что нарушает это правило и поэтому эйлеров путь невозможен.