Consider a road network of this country as a graph. Denote the chain of maximum length by $L$ in this graph. Denote $L$ by sequence of connected vertices $A_1 \to A_2 \to \dots \to A_n$.

Fig.27

That is, all other chains have the same or less length as $L$. Obviously, there is at least one outside vertex, for instance, some $A_0$, that is outside chain $L$. Besides, as the graph is connected, we can obtain a chain which connects $A_0$ with one of the vertices of chain $L$. Define the properties of the chain obtained. Call the vertex of chain $L$ an inside one, if there are no edges outside chain $L$.

1) Vertices $A_1$ and $A_n$ are not connected with each other, otherwise there will be a chain longer than chain $L$. Really, if there is an edge $A_1A_n$ in the graph, and the vertex $A_0$ is connected with some vertex $A_i$, $i \in \{1, \dots, n\}$, then there exists the following chain $A_0 \to A_i \to A_{i+1} \to \dots \to A_n \to A_1 \to \dots \to A_{i-1}$ which is longer than chain $L$, a contradiction.

2) Vertices $A_1$ and $A_n$ are inside ones, that is, vertex $A_1$ is connected with $A_2$ and with $(m-1)$ other vertices $A_{k_1}, \dots, A_{k_m}$ where $2 < k_1 < \dots < k_m < n$. Then $n \ge m+2$.

3) Vertices with numbers $(k_1-1), \dots, (k_m-1)$ are also inside ones. Really, let there be an edge $A_1A_i$, if $A_{i-1}$ isn't an inside vertex, then there is an edge $A_{i-1}A_0'$ in the graph and vertex $A_0'$ isn't inside. Then it is possible to build a chain which is longer than chain $L$: $A_0 \to A_{i-1} \to A_{i-2} \to \dots \to A_1 \to A_i \to A_{i+1} \to \dots \to A_n$. Therefore, in this chain $L$ there are at least $(m+1)$ inside vertices.

4) As there is an outside vertex which is also connected with $m$ vertices, that are not included in inside vertices mentioned above, totally there must be at least $(2m+2)$ vertices.

Show that there is a corresponding graph with such number of vertices. Consider two groups of vertices $A_1, \dots, A_m$ and $B_1, \dots, B_{m+2}$. The graph is built in such a way that each vertex $B_i$, $i=1, \dots, m+2$ is connected with each vertex $A_j$, $j=1, \dots, m$, that is, the degree of each vertex $B_i$ equals $m$, and the degree of each vertex $A_j$ equals $(m+2)$. If there is a chain which includes all the vertices, then there must be a vertex $B_i$ after each vertex $A_j$ and vice versa, because vertices with the same letter are not connected with each other. But there are $m+2$ vertices $B_i$, so we must have at least $m+1$ vertices $A_j$, and there are less. The example given concludes our proof.

Show another proof of the existence of the chain which includes all towns if $n \le 2m+1$. Let $A_1, A_2, \dots, A_n$ be the vertices of our graph. We add one more vertex $B$ to the graph and connect vertex $B$ with all vertices $A_1, A_2, \dots, A_n$. The new graph satisfies the condition that it has vertices less than $n+1 \le 2m+2$ and the degree of each vertex more than $m+1$. According to the theorem about a Hamiltonian circuit, in the new graph there exists a Hamiltonian circuit. Therefore, we can represent its circuit as the cycle $B - A_1 - A_2 - \dots - A_n - B$. Among vertices $A_i$, $k=1, \dots, n$, we have not added vertex $B$. Then the chain $A_1 - A_2 - \dots - A_n$ is a circuit which goes round all the towns.

The example we can take from the first solution.