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

Условие:

Схема городов и дорог в некотором государстве изображена на рисунке. Можно ли обойти все города, побывав в каждом из них по одному разу?

Решение:

Покрасим вершины в красные и черный цвета.

Нетрудно видеть, что из каждого красного города можно попасть только в черный и наоборот. Значит, обходя города, их цвета чередуются. Получается, в любой момент времени мы посетим красных городов не болеем чем на 1 больше чем черных. Но заметим, что красных городов 12, а черных 10. Значит, обойти все города, побывав в каждом по одному разу, невозможно.

Ответ: Нет.