Solution:

Consider a graph $G$ whose vertices are the airports in the country. Two vertices form an edge if there is an airline between the corresponding airports. Suppose that a round trip satisfying the conditions of the problem does not exist, i.e. there is no cycle of length 4 in $G$.

If $x$ is a vertex of $G$ denote by $d(x)$ the number of neighbors of $x$. Then the number of pairs both elements of which are neighbors of $x$ equals $\binom{d(x)}{2}$. Note that every pair is counted from at most one vertex $z$, since otherwise there is a cycle of length 4.

Using the identity $\sum_{x \in G} d(x) = 72$ and the Root mean square - Arithmetic mean inequality we have

$$\begin{aligned} \binom{16}{2} = 120 & \geq \sum_{x \in G} \binom{d(x)}{2} = \sum_{x \in G} \frac{d^2(x)}{2} - \sum_{x \in G} \frac{d(x)}{2} \\ & \geq \frac{1}{32}\left(\sum_{x \in G} d(x)\right)^2 - \sum_{x \in G} \frac{d(x)}{2} \\ & = \frac{72^2}{32} - 36 = 126 \end{aligned}$$
a contradiction.