На самом деле нам надо до­ка­зать, что су­ще­ству­ет два рейса оди­на­ко­вой цены из од­но­го го­ро­да. Пред­по­ло­жим про­тив­ное. Тогда все перелёты из лю­бо­го го­ро­да имеют раз­ную цену.

Рас­смот­рим самый до­ро­гой рейс. Он самый до­ро­гой в каж­дом из своих го­ро­дов, а зна­чит су­ще­ству­ет хотя бы 98 более дешёвых перелётов. Тогда этот самый до­ро­гой рейс имеет цену т. е.

Воз­мож­ных сто­и­мо­стей, мень­ших но не мень­ших всего k. Зна­чит, в каж­дом из го­ро­дов, ко­то­рые со­еди­ня­ет самый до­ро­гой рейс, есть ещё не более k рей­сов не де­шев­ле то есть в сего их в этих двух го­ро­дах не более (не счи­тая са­мо­го до­ро­го­го). Но это зна­чит, что в какой-то из остав­ших­ся 98 го­ро­дов из обоих кон­цов са­мо­го до­ро­го­го рейса ведут рейсы ценой ниже Сле­до­ва­тель­но, если мы вос­поль­зу­ем­ся этими двумя рей­са­ми, мы смо­жем про­ле­теть между кон­ца­ми са­мо­го до­ро­го­го рейса де­шев­ле, чем этим рей­сом, что про­ти­во­ре­чит усло­вию. По­лу­чен­ное про­ти­во­ре­чие до­ка­зы­ва­ет утвер­жде­ние за­да­чи.