Nobody ?

What does $K_{r,r}$ stand for?

It is a complete bipartile graph with $r$ points in each part.

In fact $m=2r^2$. The total number of choices is $2^r* 2^r$ because each set belong to a part in the bipartite graph and that expression is less than $2*r^r*r^r$ so qed.

Thanks a lot.

Isn't $m=2\cdot \binom{r}{2}=r(r-1)$ ? Please let me know if I'm wrong @below, thanks.

We have $r$ points in each part . Let's note group A and group B these two parts.We have a complete bipartite graph so any two vertices in different group are connected by an edge . The total number of flight is the total number of edges in graph . Why $m=2r^2$? Let's note the vertices in group A $a_1, a_2 ... a_r$ and vertices in group B $b_1,b_2, ... , b_r $. So $a_1$ is connected with $b_1,b_2, ... , b_r $. ($r$ times) $a_2$ is connected with $b_1,b_2, ... , b_r $. ($r$ times) $a_n$ is connected with $b_1,b_2, ... , b_r $. ($r$ times) It result $r^2$ times. Because the cities are connected by a direct (two way) flight we have $2r^2$.

Consider all pairs $(A, B)$ satisfying the following: There exists two disjoint groups of cities $P, Q$, each of size $r$. $A$ consists of $r$ flights. No two flights share the same city, be that origin or destination. All flights in $A$ connect a city in $P$ to a city in $Q$. $B$ is the ordered pair $(P, Q)$. Any such pair is considered relevant. Now, consider any $r$ flights. It belongs to at most $2^r$ relevant pairs. To see this, note that if they are not disjoint (some city belongs to two flights), then clearly they don't belong in any relevant pair. And if they are disjoint, then we can obtain $P, Q$ by picking, for each flight, which city is in $P$ (and the other will be in $Q$). There are $2^r$ such $P, Q$. It's possible that not all of them will work, but we know there are at most $2^r$ choices. On the other hand, consider any valid choices of $P, Q$ such that every city in $P$ is connected to every city in $Q$. Any such $P, Q$ belongs in $r!$ relevant pairs: permute the cities in $Q$ and pair them up with cities in $P$ in that order to give the desired $r$ flights. Suppose there are $k$ ways to pick $P, Q$ as desired. Then we have $k \cdot r! \le 2^r \cdot m^r$ by double-counting the number of relevant pairs as described above. Since $2^r \le 2 \cdot r!$, we have $k \le 2 \cdot m^r$.