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

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

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

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

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

Таким образом, мы рассмотрели все случаи и в тех из них, которые возможны, убедились в справедливости утверждения задачи.