Сириус. Комбинаторика. 7 класс. Введение в графы

В графе 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

Остальные задачи раздела