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

Рассмотрим вариант решения задания из учебника Бунимович, Булычев 10 класс, Просвещение: 93. В некотором графе все вершины имеют степень 3. Докажите, что в нём есть цикл. *Цитирирование задания со ссылкой на учебник производится исключительно в учебных целях для лучшего понимания разбора решения задания. 10 bunimovich10 93 95

Предположим, что в данном графе нет циклов. Тогда граф является лесом, то есть каждая его связная компонента — дерево.

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

По условию же все вершины графа имеют степень $$3$$, то есть вершин степени $$1$$ нет. Значит, предположение неверно.

Следовательно, в графе обязательно есть цикл.

Ответ

В графе есть цикл.