Соединим каждый город с городами, где подняли один и тот же по цвету флаг, ребрами. Тогда после смены цвета флага в городе Х на новый количество ребер между городами, где поднят один и тот же по цвету флаг, увеличивается на 1. Таким образом, этот процесс не может продолжаться бесконечно, так как количество ребер между городами с одинаковыми по цвету флагами не может быть больше, чем количество ребер во всем графе, которое конечно.