Câu hỏi 108
Ở một quốc gia nào đó, hệ thống của các hãng hàng không được kết nối (nghĩa là từ mỗi thành phố có thể đến thành phố khác bằng một số chuyến bay). Có vẻ như đối với mỗi tuyến đường tuần hoàn có một số lẻ các hãng hàng không không được kết nối. Chứng minh rằng một người có thể phân phối tất cả các thành phố thành 4 khu vực để mỗi hãng hàng không liên kết hai thành phố từ các khu vực khác nhau. (Một khu vực có thể không chứa thành phố.) (V. Dol'nikov) Trong nước, một số thành phố được kết nối bằng các chuyến bay thẳng hai chiều. Đồng thời, từ bất kỳ thành phố nào bạn có thể bay đến bất kỳ nơi nào khác (có thể có chuyển khoản). Được biết, nếu bạn chọn bất kỳ tuyến đường nào từ một số chuyến bay lẻ và đóng tất cả các chuyến bay này, thì sẽ không thể đến bất kỳ thành phố nào khác từ bất kỳ thành phố nào. Chứng minh rằng tất cả các thành phố có thể được chia thành 4 nước cộng hòa để bất kỳ chuyến bay nào kết nối các thành phố từ các nước cộng hòa khác nhau. (Một số nước cộng hòa có thể không chứa thành phố.) (V. Dolnikov)