Question

Consider an air traffic system with 6 airlines suppose that
1) Direct service between two cities means round trip direct service
2) Each pair of cities has direct service from at least one air line.

Suppose also that no airline can schedule a cycle through an odd number of cities, what is the maximum number of cities in the system?

Answer 1

each pair is participating so it is a complete graph, K, we need to divide this complete graph into 6 bipartite graphs since bipartite graph doesn't have an odd cycle  maximum cities are 2^6=64