Question 75
A certain country wishes to interconnect $2021$ cities with flight routes, which are always two-way, in the following manner:
- There is a way to travel between any two cities either via a direct flight or via a sequence of connecting flights.
- For every pair $(A, B)$ of cities that are connected by a direct flight, there is another city $C$ such that $(A, C)$ and $(B, C)$ are connected by direct flights.
Show that at least $3030$ flight routes are needed to satisfy the two requirements.
- There is a way to travel between any two cities either via a direct flight or via a sequence of connecting flights.
- For every pair $(A, B)$ of cities that are connected by a direct flight, there is another city $C$ such that $(A, C)$ and $(B, C)$ are connected by direct flights.
Show that at least $3030$ flight routes are needed to satisfy the two requirements.