Упр.79 ГДЗ Бунимович Булычев 10 класс (Алгебра)

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

Рассмотрим эйлеров цикл в мультиграфе. По определению, он проходит по каждому ребру ровно один раз и возвращается в исходную вершину.

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

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

Следовательно, степени всех вершин мультиграфа чётные.

Ответ

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