49th Mathematical Olympiad in Ukraine

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 \cdots \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_1{A}_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 \cdots \to A_n\to A_1\to \cdots \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<\cdots <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_1{A}_i$, if $A_{i-1}$ isn't an inside vertex, then there is an edge $A_{i-1}{A}_0^{\prime }$ in the graph and vertex $A_0^{\prime }$ 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 \cdots \to A_1\to A_i\to A_{i+1}\to \cdots \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.

---

Alternative solution.

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-\cdots -A_n-B$. Among vertices $A_i$, $k=1,\dots ,n$, we have not added vertex $B$. Then the chain $A_1-A_2-\cdots -A_n$ is a circuit which goes round all the towns.

The example we can take from the first solution.