5. In the country, there are 15 cities, some of which are connected by air routes belonging to three airlines. It is known that even if any one of the airlines ceases operations, it will still be possible to travel from any city to any other (possibly with layovers), using the flights of the remaining two airlines. What is the minimum number of air routes that can exist in the country?
5. We will prove that fewer than 21 airlines are not sufficient. First, note that if 15 cities are connected by airlines in such a way that one can travel from any city to any other, then there are no fewer than 14 airlines. Indeed, starting from an arbitrary city, we will try to visit all the others, and visiting each subsequent city will require at least one new airline (see fact 3).

Let the number of lines of the airlines be denoted by $a$, $b$, and $c$. By the proven fact, any two companies together have no fewer than 14 lines, i.e., $a+b \geqslant 14, b+c \geqslant 14, c+a \geqslant 14$. Adding these inequalities, we get: $2(a+b+c) \geqslant 42$, i.e., the three companies together have no fewer than 21 airlines.

It remains to provide an example with 21 airlines. Two such examples are shown in Fig. 157.

![](https://cdn.mathpix.com/cropped/2024_05_21_6455f48598646f41a890g-317.jpg?height=254&width=717&top_left_y=1379&top_left_x=332)

Fig. 157