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