MathDB

There are several cities in a country. Some pairs of the cities are connected by a two-way airline of one of the

N

companies, so that each company serves exactly one airline from each city, and one can travel between any two cities, possibly with transfers. During a financial crisis,

N-1

airlines have been canceled, all from different companies. Prove that it is still possible to travel between any two cities.

Problem Statement