Problem

Source: Vietnam TST 2019 Day 1 P1

Tags: combinatorics



In a country there are $n\geq 2$ cities. Any two cities has exactly one two-way airway. The government wants to license several airlines to take charge of these airways with such following conditions: i) Every airway can be licensed to exactly one airline. ii) By choosing one arbitrary airline, we can move from a city to any other cities, using only flights from this airline. What is the maximum number of airlines that the government can license to satisfy all of these conditions?