Licensing airways for airlines
Source: Vietnam TST 2019 Day 1 P1
March 31, 2019
combinatorics
Problem Statement
In a country there are 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?