В графе 18 вершин, причём степень каждой вершины равна 2 или 5, вершины обеих степеней присутствуют. Сколько компонент связности может быть в таком графе?
Во-первых могут быть связаны все вершины. Это 1 компонента связности.
Потом мы можем отделить 3 вершины, у которых степени будут по 2 и они образуют треугольный подграф, а остальные 15 вершин будут все связаны между собой. Это 2 компоненты.
Мы можем отделить 2 таких треугольника. Останется 12 связанных вершин, среди которых будет хотя бы одна вершина со степенью 5. Это будет 3 компоненты.
Ничего не мешает взять и 3 таких треугольника. Останется 9 вершин в большой компоненте. Это будет 4 компоненты связности.
Отлично, отделяет 4 треугольника. Остается 6 вершин. 5 компонент связности.
Больше отделять не можем - 6 вершин это минимально возможный граф, в котором может быть степень вершины 5.
Ответ: 1, 2, 3, 4, 5
