(good way: a way between two city with at most two flights (edges)) First consider one of our cities for example $A$. then some of the cities are connected to $A$ directly (by one edge) consider $k$ cities are in this case and obviously they aren't connected to each other because of the number of good way between these cities and $A$. the others don't have a direct way to $A$ so they should be connected with one of the $k$ cities and notice that they couldn't be connected to two of them because in that case we have more than one good way between this vertex(city) and $A$ so they are connected to exactly one of the $k$ cities. now put these $k$ cities be $t_1,t_2,...,t_k$ claim 1: the degree of all these $k$ cities are equal. Consider our claim is wrong so for example the degrees of $t_1,t_2$ are different. and the degree of $t_1$ is greater ($A$ is connected to both of them so we don't consider it) the cities which are connected to $t_1$ :$a_1,a_1,...,a_s$ the cities which are connected to $t_2$ :$b_1,b_2,...,b_t$ same as previous reasoning each of $a_i$ should be connected to exactly one of the $b_i$ (good way between $a_i$ and $t_2$)and also we don't have any $a_i,a_j$ which are connected to the same $b_i$ so we get that $s=t$ so the degree of all of the $k$ cities is $s$. claim 2: $k=s$ We say each $t_i$ with its cities (the cities which are connected to it by one edge) $T_i$ as a group just consider one of the cities in $T_1$ except $t_1$ as $n$ it should have a good way to all users of $T_2$ (it don't have any new idea you can check it ask if not) the degree of n is $k$ and with each degree it covers one mamber of $T_2$ so $k=s$ So totally we have $s^2+1$ cities as we want

Consider one city and denote $N$ the set of his neighbours and let |N|=a.Two cities are neighbours iff they are directly connected and the distance beetwen two cities is the lenght of the shotrest path beetwen two cities. First,it is obvious that two cities from $N$ can't be directly connected and that there isn't a city to which both cities from $N$ are connected with(in other words,we can't have a cycle of lenght $3$ or $4$). Now,denote cities $Ni$($i=1,,..a$) and denote the set of their neighbours as $Qi$.Now,consider some $Qi$ and $Qj$.Now,consider a city from $Qi$.It must have at least one neighbour from $Qj$(else the distance beetween it and $Nj$ will be more than $2$) and it can't have $2$ neighbours from it cause then we will have a cycle of lenght $4$,so we conclude that every city from $Qi$ has exactly one neighbour from $Qj$ and vica versa,so $Qi$ and $Qj$ have the same number of elements. So,by this we proved that any two cities which aren't directly connected have the same number of neighbours.We know that all $Ni$ have the same degree and all $Qi$($i=1,2...a$) and our picked city have the same degree,but there clearly exist a city in $Nj$ which isn't connected with some city in $Qi$ so we conclude all of them have the same degree,so we have $1+a+a*(a-1)=a^2+1$ cities.

When I was doing this problem I managed to show that all of the neighbors have degree a, as does the one city we picked, and furthermore that every (what you called) Ni has equal degree, but I wasn't quite able to get that all the degrees of the Ni are a. I don't understand too well what you are saying junioragd, would you mind explaining in greater detail?

You can do this for every vertex,so by doing this you proved for every $2$ that aren't connected that have equal degree(cause there will exist a vertex which is connected with both) and now it is obvious that there must exist a vertex from $Ni$ and a vertex from $Qj$($i!=j$) such that they aren't connected,so they have equal degree.Also,we proved that every vertex from $Qi$ and our picked vertex have the same degree and all $Ni$ have equal degree,so all of them have equal degree.