|
|
 |
Условие
В стране 100 городов, некоторые пары городов соединены дорогами. Для каждых четырёх городов существуют хотя бы две дороги между ними. Известно, что не существует маршрута, проходящего по каждому городу ровно один раз. Докажите, что можно выбрать два города таким образом, чтобы каждый из оставшихся городов был соединен дорогой хотя бы с одним из двух выбранных городов.
Решение
Рассмотрим граф, вершины которого соответствуют городам, а рёбра
– дорогам. Выберем в этом графе самый длинный путьS, пусть вершиныA и B – концы этого пути. Из условия следует, что в пути S не более 99 вершин.
Отметим, что концы пути S – вершины A и B – не могут быть смежны с вершинами не из S (иначе путь можно удлинить). А в случае, когда вершины A и B смежны и наш путь замыкается в цикл, никакая вершина пути S по аналогичным причинам не может быть смежна с вершиной не из S. Рассмотрим два случая.
1) В S не более 98 вершин. Рассмотрим любые две вершины Y1 и Y2, не входящие в путь S, и концы
пути A и B. Среди этих четырёх вершин должны быть проведены хотя бы два ребра. Так как ни A, ни B не могут быть смежны с вершинами
не из S, то A и B соединены ребром.
Таким образом, путь S замыкается в цикл, и тогда ни одна из вершин пути S не смежна с вершиной не из S.
Рассмотрим четвёрку из любых двух вершин X1 и X2 пути S и любых двух вершин Y1 и Y2, не входящих в S. Так как между этими четырьмя вершинами проведено хотя бы два ребра, то одно из них соединяет X1 и X2, а другое – Y1 и Y2. Таким образом, в рассматриваемом случае все вершины пути S попарно смежны и все вершины не из S также попарно смежны. Отсюда очевидно следует утверждение задачи.
2) Вне пути S лежит ровно одна вершина D.
Если D не смежна ни с одной из вершин пути S, то рассмотрим D и любые три вершины пути S. Поскольку среди этих четырёх вершин проведено хотя бы два ребра, то среди любых трёх вершин пути S проведено хотя бы два ребра. Следовательно, для любой вершины из S есть не более одной не смежной с ней вершины пути S . Поскольку 99 вершин пути S нельзя разбить на пары не соединённых ребром, то в S должна быть вершина, смежная со всеми остальными вершинами S. Эта вершина в паре с D удовлетворяет утверждению задачи.
Если концы максимального пути A и B смежны, то, как мы доказали, вершина D не смежна ни с одной из вершин пути S, а этот случай уже разобран.
Остается рассмотреть случай, когда концы пути S не смежны
и вершина D смежна хотя бы с одной из вершин X пути S. Рассмотрим вершины A, B, D и произвольную четвёртую вершину Z (естественно, лежащую на пути S).
Так как A, B и D попарно не смежны, то Z смежна хотя бы с двумя вершинами из A, B и D. Одна из соседних с X вершин пути S не является концом пути. Можно считать, что это первая вершина Y, лежащая на пути из X в B по рёбрам S.
Если Y смежна с D, то, пройдя от A к X по пути S, далее по рёбрам XD и DY и затем по пути S от Y к B, мы обойдём все вершины нашего графа ровно по одному разу, что невозможно по условию.
Если же Y не смежна с D, то, как мы доказали, эта вершина смежна и с A и с B. Тогда пройдём по ребру DX, далее по пути S от X к A, по рёбрам AY и YB, и затем по пути S от его конца B до вершины, соседней с Y на пути S, – снова получился путь, проходящий по каждой вершине нашего графа ровно один раз.
