10.3. In a country with $N$ cities, some pairs of cities are connected by two-way air routes, with no more than one route between any pair. Each air route belongs to one of $k$ companies. It turned out that from any city, one can reach any other city (possibly with layovers), but if all the air routes of any company are closed, this property is violated. What is the maximum number of air routes (for arbitrary $N$ and $k$) that could exist in this country?

(S. Berlov, N. Vlasova)
Answer. The construction is possible only for $k<N$, and then the maximum number of edges is $C_{N}^{2}-C_{k}^{2}$.

First Solution. Consider a graph where the vertices are cities, and the edges are air routes, with edges corresponding to air routes of the $i$-th company colored in the $i$-th color.

Example. Suppose in the graph, vertices $v_{1}, \ldots, v_{k}$ are not adjacent to each other, and from vertex $v_{i}$, there are edges of color $i$ to all vertices with numbers greater than $k$. All edges between vertices with numbers greater than $k$ are present and colored arbitrarily. Clearly, when edges of color $i$ from vertex $v_{i}$ are removed, it is impossible to reach the other vertices of the graph, while the initial graph is connected.

Estimate. We will prove by induction on $k$ that the graph lacks at least $C_{k}^{2}$ edges; from this it follows that $k<N$, otherwise there would be no edges, and the graph would not be connected. The base case for $k=1$ is obvious.

Inductive step: $(k-1) \mapsto k$. Consider all connected components of color $k$. There are at least $k$ of them, otherwise, by adding colors, we can reduce the number of components by at least 1 each time (if adding a color does not reduce the number of components, then removing edges of that color from the original graph leaves the graph connected). Then, the $(k-1)$-th color already makes the graph connected.

Contract each connected component of color $k$ into a vertex (i.e., map each component to a vertex of a new graph, drawing edges between vertices if and only if some vertices of the corresponding components were connected by an edge; if there were edges of several colors between two components, leave one). The resulting graph satisfies the inductive hypothesis, so it lacks at least $C_{k-1}^{2}$ edges, corresponding to at least the same number in the original graph.

On the other hand, if all edges of color $k$ are removed, at least one of its components, say $C$, must split into two. This means that there are no edges from one of the parts of $C$ to any other component $D$. We will prove that this implies the absence of at least $k-1$ more edges not previously accounted for. If there are no edges from component $D$ to both parts of $C$, then this means the absence of at least two edges, while we previously accounted for only one. If there is an edge from component $D$ to one of the parts of $C$, then in the graph of contracted components, the corresponding components were connected, but in the original graph, there is no such edge. Thus, for each component other than $C$, we must account for the absence of at least one more edge. Therefore, at least $k-1$ more edges are missing, and the total number of missing edges is at least $C_{k-1}^{2} + (k-1) = C_{k}^{2}$, as required.

Second Solution. We will provide another way to prove the estimate; we use the terminology introduced at the beginning of the first solution.

First, we prove that for each pair of companies $(i, j)$, there exist two vertices $A, B$ such that any path between them contains edges of both companies $i$ and $j$. Suppose that upon removing company $i$, the vertices split into two non-empty sets $U_{i}$ and $V_{i}$, with no edges between them, and upon removing company $j$, they split into sets $U_{j}$ and $V_{j}$. If the sets $U_{i} \cap U_{j}$ and $V_{i} \cap V_{j}$ are both non-empty, then we can take $A \in U_{i} \cap U_{j}$ and $B \in V_{i} \cap V_{j}$. Otherwise, the sets $U_{i} \cap V_{j}$ and $V_{i} \cap U_{j}$ are both non-empty, and we can take $A \in U_{i} \cap V_{j}$ and $B \in V_{i} \cap U_{j}$. It is clear that $A$ and $B$ are suitable and that there is no edge between them.

For each pair of companies $(i, j)$, choose $A$ and $B$ such that the distance between them (i.e., the length of the path along the edges of the original graph) is minimal. If we prove that different pairs of companies correspond to different pairs $(A, B)$, then we will have that the number of missing edges is at least the number of pairs of companies, which gives the required estimate.

Suppose that the pair $(A, B)$ corresponds to two different pairs of companies - $(1,2)$ and another (without loss of generality, either $(1,3)$ or $(3,4))$. Let $A=A_{0}, A_{1}, \ldots, A_{n-1}, A_{n}=B$ be one of the shortest paths between $A$ and $B, n \geqslant 2$. If the edge $A_{0} A_{1}$ belongs to neither company 1 nor 2, then any path between $A_{1}$ and $A_{n}$ contains edges of companies 1 and 2, which contradicts the minimality of the distance for the pair $(A, B)$. Similarly, the edge $A_{n-1} A_{n}$ belongs to one of companies 1 or 2.

Thus, the pair $(A, B)$ cannot correspond to the pair of companies $(3,4)$. Therefore, the pair $(A, B)$ corresponds to the pair of companies $(1,3)$, and the edges $A_{0} A_{1}$ and $A_{n-1} A_{n}$ both belong to company 1. Then any path between $A_{0}$ and $A_{n-1}$, any path between $A_{n-1}$ and $A_{1}$, and any path between $A_{1}$ and $A_{n}$ contain edges of both companies 2 and 3. From the minimality of the distance for the pair $(A, B)$, it follows that there exist paths between $A_{0}$ and $A_{n-1}$, between $A_{n-1}$ and $A_{1}$, and between $A_{1}$ and $A_{n}$ that do not contain edges of company 1. By connecting these paths, we obtain a path (possibly with repeated vertices) from $A_{0}$ to $A_{n}$ that does not contain edges of company 1. Contradiction.