IRL_ABooklet

Question

The country of Cathay has four cities with airports and two Airlines Cathay Red and Cathay Blue. Each of the six routes is assigned to only one of the airlines. No airline is assigned all the routes. An assignment of routes is called good if there are two cities for which the airline that operates the route between the two is different from the airline that operates the route between the other two cities. Show that there is an assignment of routes which is not good.

Accepted Answer

The problem can be expressed in graph theory terms as colouring the edges of the graph

K_{4}

, the complete graph on 4 vertices. There is essentially one colouring which is not good, namely:

The dashed line represents one colour and the solid line the other. Interchanging the top vertices or the colours gives other representations of essentially the same solution.