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

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 80. Докажите, что если степени всех вершин мультиграфа чётные, то в нём есть эйлеров цикл (достаточное условие в теореме Эйлера).

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

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

Следовательно, движение по неиспользованным рёбрам можно продолжать до тех пор, пока мы не вернёмся в начальную вершину. Получится замкнутый цикл.

Если при этом остались неиспользованные рёбра, то из некоторой вершины уже построенного цикла, инцидентной таким рёбрам, можно начать новый цикл и «вставить» его в первый. Повторяя этот процесс, получаем замкнутый маршрут, проходящий по каждому ребру ровно один раз.

Такой маршрут и является эйлеровым циклом.

Ответ

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