В поисках неизведанного

Маршруты, о которых говорится в данной задаче — гамильтоновы пути. То есть пути, которые проходят через каждую вершину данного графа ровно по одному разу. Заметим, что если путь w подходит, то «развернутый» путь (вершины в котором следуют в обратном порядке) — тоже подходит, так как пути считаются различными, если последовательности вершин в них неодинаковы.

Тогда общее количество таких путей всегда четно. Кроме случая когда n = 1, тут ответ, очевидно, равен 1.