Câu hỏi 124
Một Vương quốc gồm $N$ thành phố, một số cặp thành phố được nối với nhau bằng các con đường đôi một không cắt nhau (hai thành phố được nối bằng một con đường gọi là hai thành phố *kề nhau*). Từ mỗi thành phố có thể đi đến mọi thành phố khác qua các con đường, nhưng không thể quay trở lại thành phố xuất phát nếu mỗi con đường được đi không quá một lần.
Một lần nhà Vua thực hiện cải cách: mỗi một trong $N$ vị Thị trưởng trở thành Thị trưởng của một trong $N$ thành phố, có thể không phải thành phố mà ông làm việc trước cải cách. Biết rằng hai Thị trưởng bất kỳ làm việc ở hai thành phố kề nhau trước cải cách thì sau cải cách cũng làm việc ở hai thành phố kề nhau. Chứng minh rằng hoặc tồn tại một thành phố có cùng một Thị trưởng trước và sau cải cách, hoặc tồn tại một cặp thành phố kề nhau đã hoán đổi Thị trưởng cho nhau.
Một lần nhà Vua thực hiện cải cách: mỗi một trong $N$ vị Thị trưởng trở thành Thị trưởng của một trong $N$ thành phố, có thể không phải thành phố mà ông làm việc trước cải cách. Biết rằng hai Thị trưởng bất kỳ làm việc ở hai thành phố kề nhau trước cải cách thì sau cải cách cũng làm việc ở hai thành phố kề nhau. Chứng minh rằng hoặc tồn tại một thành phố có cùng một Thị trưởng trước và sau cải cách, hoặc tồn tại một cặp thành phố kề nhau đã hoán đổi Thị trưởng cho nhau.