Team Selection Test

The answer is $34$. Let $A_1,A_2,\dots ,A_{35}$ be cities so that only $A_i$ and $A_{i+1}$ are connected for $i=1,2,\dots ,34$. The travel between $A_1$ and $A_{35}$ uses at least $34$ flights. After adding flights between $A_1$ and $A_{35}$, it is possible to travel between any pair of cities by using at most $17$ flights. Therefore, the answer is at least $34$.

Let us show that $34$ flights are sufficient. Let $\rho (X,Y)$ denote the minimal possible number of flights between the cities $X$ and $Y$. On the contrary, suppose that $\rho (A,B)>34$ for some cities $A$ and $B$ and a path with minimal number of flights before adding a flight between the cities $T$ and $S$ is $(A=A_0,A_1,\dots ,A_{17},A_{18},\dots ,B=A_k)$. After adding the flight between $T$ and $S$, $\rho (A,A_{18})\le 17$ and $\rho (A_{17},B)\le 17$. By definitions, both of the paths with minimal number of flights from $A$ to $A_{18}$ and from $A_{17}$ to $B$ have to use the flight between $T$ and $S$. Without loss of generality we may assume that the path from $A$ to $A_{18}$ is $(A_0,\dots ,T,S,\dots ,A_{18})$. Then note that $l_1+l_2\le 16$ where $\rho (A,T)=l_1$, $\rho (S,A_{18})=l_2$.

Similarly, the path from $A_{17}$ to $B$ is $(A_{17},\dots ,T,S,\dots ,B)$ with $\rho (A_{17},T)=m_1$, $\rho (S,B)=m_2$ and $m_1+m_2\le 16$, or the path from $A_{17}$ to $B$ is $(A_{17},\dots ,S,T,\dots ,B)$ with $\rho (A_{17},S)=k_1$, $\rho (T,B)=k_2$ and $k_1+k_2\le 16$. Then there exists a travel from $A$ to $B$ $(A,\dots ,T,\dots ,A_{18},A_{17},\dots ,S,\dots ,B)$ using at most $l_1+m_1+1+l_2+m_2<34$ flights or $(A,\dots ,T,\dots ,B)$ using at most $l_1+k_2<34$ flights. Contradiction.