MathDB

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.

Problem Statement