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

Решим простую задачу на графы, которая на первый взгляд такой не кажется. Сначала читаем развесистое условие и пытаемся понять, что требуется в задаче: Если переложить на язык алгоритмов, то надо покрыть граф путями. И есть специальные алгоритмы, которые справляются с этой задачей. Но они расчитаны на ориентированные графы. А в этой задаче по каждой дороге можно передвигаться в обоих направлениях. Если упростить задачу и сказать, что есть только один ковбой и спросить, можно ли заблокировать все дороги? Тогда мы получим вариант классической загадки про нарисовать фигуру, не отрывая руки...