17. The diagram is a "map" of Jo's local rail network, where the dots represent stations and the lines are routes. Jo wants to visit all the stations, travelling only by train, starting at any station and ending at any station, with no restrictions on which routes are taken.

What is the smallest number of stations that Jo must go to more than once?
A 1
B 2
C 3
D 4
E 5
Solution
C We label the stations as shown in the diagram on the right so that we can refer to them. Jo can visit the stations in the order
$$
O, P, Q, R, S, R, T, X, Y, Z, Y, X, W, V, U \text {. }
$$

In this way she visits all the stations and goes through just three of them, $R, Y$ and $X$ more than once.

It remains only to show that Jo cannot visit all the stations without going through at least three of them more than once.

Jo must go through the junction stations $R$ and $X$ more than once. If Jo does not start or finish at $O$, she will have to go through $P$ more than once. If she does not start or finish at $U$ she will have to go through $V$ more than once. If she starts at $O$ and finishes at $U$, or vice versa , she will have to go through $Y$ more than once. It follows that Jo has to go through at least three stations more than once. So this is the smallest number of stations Jo must go through more than once.