Формальная постановка задачи: нужно покрасить кактус в три цвета, и при этом минимизировать количество вершин третьего цвета, либо сообщить, что данный кактус нельзя покрасить в три цвета. Несложно заметить, что кактус всегда можно покрасить в три цвета. Для того, чтобы найти минимальное необходимое количество вершин третьего цвета, воспользуемся методом динамического программирования. Построим дерево обхода кактуса dfs-ом. Теперь для каждого поддерева будем считать минимальное количество вершин третьего цвета, которое нужно, чтобы покрасить поддерево в три цвета, и для всех ребер, лежащих целиком в поддереве, цвета концов были различны. Заметим, что благодаря тому, что граф является кактусом, из каждого поддерева наверх ведут максимум два ребра: одно из корня поддерева в его родителя, и максимум одно ребро не из дерева обхода. Поэтому, дополнительно в состояние нужно добавить только цвета двух нижних вершин этих рёбер. В итоге, получаем линейное число состояний, пересчёт для вершины работает за количество её детей, что в сумме по всем вершинам равно линии. Получается линейное решение с достаточно большим константным множителем.