Câu hỏi 89
Một số thành phố của đất nước gồm $n$ thành phố được nối bằng các chuyến bay khứ hồi sao cho từ mỗi thành phố có ít nhất $k$ chuyến bay và có thể đi từ bất kỳ thành phố nào tới bất kỳ thành phố nào. Chứng minh rằng với mọi cách tổ chức như vậy, có thể phân các chuyến bay cho $n-k$ hãng hàng không sao cho đi từ thành phố bất kỳ tới thành phố bất kỳ bằng cách sử dụng nhiều nhất một chuyến bay của mỗi hãng.