Эйлеровы графы

Построим граф, вершинами которого являются перекрестки между улицами, а ребрами — сами улицы. Также условимся, что в нашем графе разрешены кратные ребра (то есть, если турист прошел дважды по одной улице, то этой улице будут соответствовать 2 ребра). Пусть мы начали прогулку в вершине , а закончили — в вершине . Оставим в графе только ребра, соответствующие улицам, пройденным нечетное количество раз.

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