Câu hỏi 70
Một quốc gia chứa các thành phố $n$ và một số thị trấn. Có nhiều nhất một con đường giữa mỗi cặp thị trấn và nhiều nhất một con đường giữa mỗi thị trấn và mỗi thành phố, nhưng tất cả các thị trấn và thành phố đều được kết nối trực tiếp hoặc gián tiếp. Chúng ta gọi tuyến đường giữa một thành phố và một thị trấn là tuyến đường vàng nếu không có tuyến đường nào khác giữa chúng đi qua ít thị trấn hơn. Chứng minh rằng chúng ta có thể chia các thị trấn và thành phố giữa các nước cộng hòa $n$, sao cho mỗi nước chỉ thuộc về một nước cộng hòa, mỗi nước cộng hòa chỉ có một thành phố và mỗi nước cộng hòa có tất cả các thị trấn trên ít nhất một trong các tuyến đường vàng giữa mỗi thị trấn và thành phố của nó.