In some country several pairs of cities are connected by direct two-way flights. It is possible to go from any city to any other by a sequence of flights. The distance between two cities is defined to be the least possible numbers of flights required to go from one of them to the other. It is known that for any city there are at most $100$ cities at distance exactly three from it. Prove that there is no city such that more than $2550$ other cities have distance exactly four from it.
This problem is from the IMO Shortlist 2013. My first thought was constructing a graph with the cities as vertices. Now we have the graph is connected. But the rest seems a bit blurry to me. Can someone help me? Thanks.
Construct a graph $G$ with a vertex corresponding to each city, and an edge between each pair of cities for which a flight between the cities exists. Consider any vertex $v \in V(G)$. Let $d_4(v)$ be the number of vertices of distance $4$ from $v$ in $G$. Let $\{v_1, v_2, \dots , v_p\}$ be the set of vertices of distance $1$ from $v$ in $G$. Now for each $i\in\{1,2,\dots,p\}$, let $V_i$ be the set of vertices $w$ not in any $V_j$ for $j<i$ at distance $4$ from $v$ for which a path of length $3$ not including $v$ exists between $v_i$ and $w$. Let $|V_i| = n_i$.
If all values of $n_i$ are zero, then $d_4(v) = 0$. So assume, without loss of generality, that $n_1, n_2, \dots, n_q$ are non-zero (if not, re-index so that this is the case). Now note that all vertices in $V_i$ are distance $3$ from $v_i$, and for each $j\in\{1,2,\dots,q\}$ different from $i$, there must be at least one additional vertex of distance $3$ from $v_i$. Now since no vertex can have more than $100$ vertices at distance $3$, we have for each $i \in \{1,2,\dots,q\}$:
$$n_i + q - 1 \leq 100$$
And we have that:
$$d_4(v) \leq \sum_{i=1}^{q} n_i \leq \sum_{i=1}^{q} (101 - q) = (101-q)q$$
But $f(q) = (101-q)q$ is maximum when $f'(q) = 101 - 2q = 0$, or when $q = \frac{101}{2}$, so we have:
$$d_4(v) \leq \left(101 - \frac{101}{2}\right)\frac{101}{2} = 2550.25$$
Thus the number of vertices at distance $4$ from any vertex is at most $2550$.