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.
Solution
The problem can be expressed in graph theory terms as colouring the edges of the graph , 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.
Want a route through all this instead of an archive? The track
puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.