Задача
В связном графе степени четырёх вершин равны 3, а степени остальных вершин равны 4.
Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности.
Решение
Пусть это удалось. Если удалённое ребро соединяло вершины с одинаковыми степенями, то в каждой полученной компоненте будет нечётное число нечётных вершин (по одной или по три), что невозможно.
Если же удалённое ребро соединяло вершины со степенями 3 и 4, то только в одной компоненте будет вершина степени 2, то есть компоненты не будут изоморфны.
Ответ
Ответ задачи отсутствует
Чтобы оставлять комментарии, войдите или зарегистрируйтесь
Комментариев нет