Question 61
Pirajuba has 10 cities, called $H_{1}, H_{2}, \ldots, H_{10}$, and some of them are connected by two-way roads. It is known that it is possible to get from $H_{1}$ to $H_{10}$. Show that one of the situations below occurs: (i) There is a path connecting $H_{1}$ to $H_{10}$ using a maximum of 3 roads. (ii) There are 2 cities $H_{i}$ and $H_{j}, 2 \leq i\lt j \leq 9$, such that all the way connecting $H_{1}$ to $H_{10}$ passes through $H_{i}$ or $H_{j}$.