В связном графе степени восьми вершин равны 3, а степени остальных вершин равны 4. Докажите, что нельзя удалить ребро так, чтобы граф распался на две изоморфные компоненты связности. Верно ли аналогичное утверждение для графов с 10 вершинами степени 3 (и произвольным количеством вершин степени 4)?

а) Предположим, что мы удалили такое ребро.
1) Если удалённое ребро соединяло вершины с одинаковыми степенями, то в каждой полученной компоненте будет нечётное число вершин с нечетной степенью, что невозможно, так как противоречит лемме о рукопожатиях
2) Если же удалённое ребро соединяло вершины со степенями 3 и 4, то только в одной компоненте будет вершина степени 2, то есть компоненты не будут изоморфны.
Б) Ответ: Верно
Если мы удалим ребро, которое соединяло вершины степени 3. Тогда в каждой компоненте стало, к примеру, 4 вершины степени 3, если изначально в каждой компоненте у нас было по 5 вершин. Значит, утверждение верно.