SELECTION and TRAINING SESSION

Answer: $1,2,\dots ,[n/2]$.

We reformulate the problem in the language of Graph Theory. Consider a graph, the vertices of which correspond to cities and the edges correspond to air connections. It is given that the graph is connected and the eccentricity of all of its vertices (the greatest of the minimal distances from it to other vertices) equals its radius (number $m$). We will show that the radius of a graph on $n$ vertices can't be greater than $[n/2]$, which will imply that $m\le [n/2]$.

Start the process of deleting edges in the graph one by one, preserving the connectivity of it, as long as possible. We will end with a tree. For a tree on $n$ vertices, the maximal length of a chain doesn't exceed $n-1$ edge, hence, it is possible to reach any vertex from a central one (or from two central ones) by $[n/2]$ steps, which implies that the radius of the tree doesn't exceed $[n/2]$. It is left to note that the radius doesn't decrease when deleting edges, so our claim is proved.

Consider now any number $m\le [n/2]$. Take a cycle of length $2m$, whose radius clearly equals $m$. Choose a vertex $v$ of a cycle and create $n-2m$ copies of it, each of which is connected only to both neighbours of $v$. Then draw an edge between any pairs of copies of $v$, and connect $v$ with all of them. Clearly, the constructed graph satisfies the problem's conditions.