In a country there are $15$ cities, some pairs of which are connected by a single two-way airline of a company. There are $3$ companies and if any of them cancels all its flights, then it would still be possible to reach every city from every other city using the other two companies. At least how many two-way airlines are there?
1. **Translate the problem to graph theory**:
   - Consider a graph \( H \) with 15 vertices, where each vertex represents a city.
   - Each edge in the graph represents a two-way airline between two cities.
   - The edges are colored according to the airline company: blue, red, and green.

2. **Define the edge sets**:
   - Let \( B \), \( R \), and \( G \) be the number of blue, red, and green edges, respectively.

3. **Establish connectivity conditions**:
   - If any one company cancels all its flights, the remaining graph (formed by the other two companies' edges) must still be connected.
   - This implies that removing all red edges leaves a connected graph, so the subgraph formed by blue and green edges must be connected. Therefore, \( B + G \geq 14 \) (since a connected graph with 15 vertices must have at least 14 edges).
   - Similarly, removing all blue edges leaves a connected graph, so \( R + G \geq 14 \).
   - Removing all green edges leaves a connected graph, so \( B + R \geq 14 \).

4. **Combine the inequalities**:
   \[
   B + G \geq 14
   \]
   \[
   R + G \geq 14
   \]
   \[
   B + R \geq 14
   \]
   - Adding these three inequalities:
   \[
   (B + G) + (R + G) + (B + R) \geq 3 \times 14
   \]
   \[
   2B + 2R + 2G \geq 42
   \]
   \[
   B + R + G \geq 21
   \]

5. **Construct a graph with 21 edges**:
   - Number the vertices \( 1, 2, \ldots, 15 \).
   - Connect the pairs \((i, i+1)\), \((3+i, 4+i)\), \((6+i, 7+i)\), \((9+i, 10+i)\), \((12+i, 13+i)\), \((2+i, 8+i)\), and \((5+i, 11+i)\).
   - Assign \( i = 1 \) for blue, \( i = 2 \) for red, and \( i = 3 \) for green.

   - This construction ensures that each company has 7 edges, and the total number of edges is \( 7 + 7 + 7 = 21 \).

   - Verify that removing any one color still leaves a connected graph:
     - Removing blue edges leaves the red and green edges, which form a connected graph.
     - Removing red edges leaves the blue and green edges, which form a connected graph.
     - Removing green edges leaves the blue and red edges, which form a connected graph.

Thus, the minimum number of two-way airlines required is 21.

The final answer is \(\boxed{21}\)