Решение задачи 117

Предположим, что такой путь существует. Тогда в таком пути есть конечная и начальная вершина. Если конечная и начальная вершина совпадают, то получаем, так называемый, Эйлеров цикл.

Рассмотрим произвольную вершину X, которая не является ни начальной, ни конечной. В какой-то момент муравей должен зайти в нее в первый раз и выйти. В таком случае по двум из трёх ребер из этой вершины уже муравей не сможет пройти в дальнейшем. Осталось ещё одно ребро из этой вершины, по нему муравей должен пройти обязательно. Причем, проходя по оставшемуся ребру, муравей обязательно попадает именно в X(он же уже вышел из X в первый раз, значит не может находиться в X, не зайдя в нее). После этого муравей уже не может идти дальше, поскольку по всем трём рёбрам из X он уже ходил. Значит он завершает свой путь именно в X. Получаем противоречие с тем, что X не является конечной.

Значит такого пути не существует.