Câu hỏi 61
Pirajuba có 10 thành phố, được gọi là $H_{1}, H_{2}, \ldots, H_{10}$, và một số thành phố được kết nối bằng đường hai chiều. Được biết, có thể chuyển từ $H_{1}$ đến $H_{10}$. Chứng minh rằng một trong những tình huống dưới đây xảy ra: (i) Có đường nối $H_{1}$ đến $H_{10}$ sử dụng tối đa 3 đường. (ii) Có 2 thành phố $H_{i}$ và $H_{j}, 2 \leq i\lt j \leq 9$, sao cho tất cả các cách kết nối $H_{1}$ với $H_{10}$ đi qua $H_{i}$ hoặc $H_{j}$.