Final Round

We use the graph theory language and consider the towns as the vertices of the graph $\Gamma$. We connect two vertices by the edge iff there exists a flight from one of them to the other town. The problem conditions are equivalent to the following conditions for the graph $\Gamma$:

i) any two different vertices are connected with a unique path consisting of at most two edges; ii) there are cyclic paths of length neither 3 nor 4 (see Fig. 1); iii) there is no vertex connected with all others.

Fig. 1

Fix any vertex $v$ of $\Gamma$ and partition all the vertices of $\Gamma$ into three sets: ${\Gamma }_0$, ${\Gamma }_1$ and ${\Gamma }_2$ (the vertices of ${\Gamma }_i$ are called the vertices of the $i$-th level, $i=0,1,2$). ${\Gamma }_0$ consists of exactly one vertex $v$; ${\Gamma }_1$ consists of all vertices connected with $v$ by the edge; ${\Gamma }_2$ consists of all remaining vertices of $\Gamma$. Let ${\Gamma }_1$ consist of vertices $v_1,v_2,...,v_k$ (see Fig. 2). From ii) it follows that no two vertices $v_p,v_q\in {\Gamma }_1$ are connected by the edge (otherwise there is a cyclic path of length 3: $v{v}_p{v}_{q}v$). From iii) it follows that ${\Gamma }_2\ne \varnothing$.

Fig. 2

Show that each vertex of the 1st level is connected with at least one vertex of the 2nd level, and the distinct vertices of the 1st level cannot be connected with the same vertex of the 2nd level. Indeed, if some vertex $v_p\in {\Gamma }_1$ is connected with none of the vertices of the 2nd level, then ($v_p$ is connected with none of the vertices of the 1st level) the path from $v_p$ to any of the vertices of the 2nd level passes through $v$ (see Fig. 2), i.e. this path consists of at least two edges, contrary to i). If two vertices $v_p,v_q\in {\Gamma }_1$ are connected with the same vertex $w\in {\Gamma }_2$, then we have the cyclic path $v{v}_{p}w{v}_{q}v$ of length 4 (see Fig. 2), contrary to ii).

Now it follows that ${\Gamma }_2=\{G_1,G_2,...,G_k\}$, $G(i)\cap G(j)=\varnothing$ for all $i\ne j$, and $G_p$ consists of those vertices of the 2nd level which are connected with $v_p$, $p=1,2,...,k$, (see Fig. 2). Prove that all $G_1,G_2,...,G_k$ contain the same number of the vertices. Consider any two sets $G_p$ and $G_q$ ($p\ne q$). Suppose that there is $w\in G_p$ which is connected with none of the vertices of $G_q$. Then there is no path from $w$ to $v_q$ with at most two edges. Indeed, we can reach $v_q$ either from $v$ or from any vertex of $G_q$. But the shortest path from $w$ to $v$ consists of two edges, and the path from $w$ to each vertex of $G_q$ consists of at least two edges. The obtained contradiction shows that each vertex of $G_p$ is connected by the edge with at least one of the vertices of $G_q$. Moreover, each vertex $w\in G_p$ is connected by the edge with exactly one vertex of $G_q$ (otherwise if $w$ is connected by the edges with $u_1,u_2\in G_q$, then we have the cyclic path $w{u}_1{v}_q{u}_{2}w$ of length 4). Since we choose $G_p$ and $G_q$ arbitrarily, it follows that all sets $G(i)$, ($i=1,...,k$) have the same number of the vertices. Let $m$ denote the number of the vertices in each set of the sets $G_1,G_2,...,G_k$.

Consider any $G_p$ and some of its vertex $w$. Since no two vertices of $G_p$ are connected by the edge (otherwise there exists a cyclic path of length 3), $w$ is connected by the edge with exactly one vertex of each of the $k-1$ of the sets $G_m$, $m\ne p$; $w$ is connected by the edge with $v_p$ and there are no edges from $w$ different from the mentioned edges, we see that the degree of $w$ is equal to $(k-1)+1=k$. Thus, the degree of each vertex of the 2nd level is equal to $k$, i.e. these degrees are equal to the number of the vertices of the 1st level.

Note that vertex $v$ is chosen arbitrarily. Hence, applying the same arguments for $v_1$, we obtain that the 1st level for $v_1$ consists of $m=1$ vertices (the 1st level for $v_1$ consists of $v$ and all vertices of $G_1$ (see Fig. 2)). Therefore, the degree of each vertex of the 2nd level for $v_1$ is equal to $m+1$.

In particular, the degree of each vertex of, for example, $G(2)$ is equal to $m+1$. On the other hand, by the above, the degree of this vertex is equal to $k$. Therefore, we obtain $m=k-1$. Thus, $\Gamma$ consists of exactly $1+k+k(k-1)=k^2+1$ vertices. The required statement is proved.



Fig. 3

Remark. There exist graphs described in the problem conditions and solution, e.g., a 5-cyclic graph 5 or the Petersen graph (see Fig. 3).