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

1. В некотором графе все вершины имеют степень 3. Докажите, что в нём есть цикл.

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

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

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

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

Ответ

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