Practical Mathematics K10In a particular country there are six big cities and three airlines. No direct air route is shared by any other airline.

What is the smallest possible number of direct air routes, if bankruptcy of any one of the three airlines still leaves all the six cities being connected (not necessarily directly)?