Деревья и остовные деревья

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