Как решить? всё перепробовал 1 и 5, 2 и 5 и 6 и 9

Денис Лазарев, 4 года назад
Мастер

Пусть граф неориентированный, без петель.
Есть компонента связности с 6 или более вершинами, так как есть вершина степени 5. Каждая компонента связности содержит 3 или более вершин, так как степень вершины не менее 2.
Поэтому м. б. 5,4,3,2,1 компоненты связности.
Например, 5: полный граф на 6 вершинах и 4 полных графа на 3 вершинах,
4: полный граф на 6 вершинах, 2 полных графа на 3 вершинах и цикл на 6 вершинах и т. д.
Ответ: от 1 до 5 компонент связности