Граф со степенью вершин 3 и наличие цикла — олимпиадная задача
В графе все вершины имеют степень 3. Докажите, что в нём есть цикл.
Разобрать решение
Рассмотрим произвольную компоненту связности этого графа. Она не является деревом, так как в ней нет висячей вершины (см. задачу 130786). Значит, в ней есть цикл.
Обсуждение
0Комментариев пока нет.
Чтобы оставить комментарий, войдите в аккаунт.