MathDB

P1

Part of 2019 Vietnam TST

Problems(1)

Licensing airways for airlines

Source: Vietnam TST 2019 Day 1 P1

3/31/2019
In a country there are n≥2n\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?
combinatorics