Question: Suppose the 10 cities are divided into 4 distinct groups G1, G2, G3, G4 having 3, 3, 2 and 2 cities respectively and that G1 consists of cities named A, B and C. Further suppose that direct flights are allowed only between two cities satisfying one of the following:
Both cities are in G1
Between A and any city in G2
Between B and any city in G3
Between C and any city in G4
Then the minimum number of direct fights that satisfies the underlying principle of the airline is:
Now A, B and C are in G1. As there is no restriction of flights that can connect with each other in G1, the total number of flights connecting 2 cities in G1 is 3 C2 × 4
Total minimum number of direct flights that satisfy the underlying principle is 12 + 12 + 8 + 8 = 40