Hopefully understood the question correctly. The answer is $k=1$. We claim that there can exist only one company for every complete graph with $N$ nodes. Assume $k=2$ is possible. Now, as one company should not form a connected graph, there exists a node such that it does not belong to the first company, however as we have a complete graph, every edge from this node belongs to the second company, forming a connected graph, a clear contradiction. Now assume $k\geq 3$ is possible, then we group some colours and reduce the number of colours to number $2$ and by this argument, $k=2$ must also be possible, however by the claim, it is not, therefore $k\geq 3$ is also impossible. We are done.

rafaello wrote: Hopefully understood the question correctly. The answer is $k=1$.

for every complete graph with $N$ nodes.

I think the underlying graph can be any connected graph $G$ on $N$ vertices since here being able to travel precisely means to find a path and not necessarily an edge. But I could not follow your solution rafaello, because you mention "no node must belong to the second company", but here the whole point is that the companies do not own nodes (or airports), they own the edges (or the airplanes which travel across these routes). I think I have an example with $N=4$ where there is a solution with $2$ companies; let the cities be $c_1, c_2, c_3, c_4.$ Join $c_1,c_2$ by an airplane of company 1, $c_1, c_4$ by an airplane of company 1, $c_2, c_3$ by an airplane of company 2, $c_2, c_4$ by an airplane of company 2, and finally $c_4, c_3$ by an airplane of company $4.$ If you remove company 1 airlines then $c_1$ cannot be reached anymore, while if you remove company $2$ airlines then $c_3$ cannot be reached anymore.

Draw the complete graph on $N$ nodes where each edge has a colour in $\{0,1,2,\ldots,k\}$. Colour $i$ = airline $i$, and $0$ = no route between that pair of cities. You can go from anywhere to anywhere iff there exists a spanning tree. Any such spanning tree has $N-1$ edges, each of which must include all positive edge colours. So $k\le N-1$. Can $k=N-1$? Yes. Just have a single spanning tree. (No pair of cities off the tree is connected by any airline.)

A colour corresponds to a company, and we were told the removal of any colour disconnects the graph, each colour contains an edge cut. We just need to find the maximum number of edges in an $n $-vertex graph with at least $k $ pairwise disjoint edge cuts.

This solution does not answer to maximise the edges. It maximises colours $k $. It doesn't find the maximum number of the edges, the graph can have for $n,k. $

Physicsknight wrote: A colour corresponds to a company, and we were told the removal of any colour disconnects the graph, each colour contains an edge cut. We just need to find the maximum number of edges in an $n $-vertex graph with at least $k $ pairwise disjoint edge cuts.

This solution does not answer to maximise the edges. It maximises colours $k $. It doesn't find the maximum number of the edges, the graph can have for $n,k. $ yeah, sorry

Following is an answer to a wrongly understood question, do read the subsequent posts (eg: #10) for details.

I think all arguments above do not answer the question. Which is to determine the maximum possible number of airlines. This number depends on $k$ and $N$. So, the question is not to find the maximum possible value of $k$ (which is $N-1$). In this problem $N$ and $k$ ($1\le k\le N$) are fixed and we look for the maximum number of edges, so that such a construction is possible.

dgrozev wrote: I think all arguments above do not answer the question. Which is to determine the maximum possible number of airlines. This number depends on $k$ and $N$. So, the question is not to find the maximum possible value of $k$ (which is $N-1$). In this problem $N$ and $k$ ($1\le k\le N$) are fixed and we look for the maximum number of edges, so that such a construction is possible. That sounds tricky. In being sloppy I read "what is the maximum number of airline companies that can operate?", but for the question you ask I think an easy observation leads to the answer, because in that case we can take the complete graph $K_N$ on $N$ vertices as $G$ and make all the aeroplanes of the same company, thus yielding the maximum number of edges to be $\binom{N}{2}.$

adityaguharoy wrote: ..., but for the question you ask I think an easy observation leads to the answer, because in that case we can take the complete graph $K_N$ on $N$ vertices as $G$ and make all the airlines of the same company, thus yielding the maximum number of edges to be $\binom{N}{2}.$ You cannot make all the airlines belong to only one company (and all the others to operate on empty set of edges) because it does not comply with the problem condition. If you remove an dummy company the graph would be still connected. So, the question is exactly as written, and it makes sense, and the problem is far from being trivial.

Ok, so a sketch of the official solution. The answer is $N(N-1)/2-k(k-1)/2$. Lemma: For any pair of colors $(i, j)$, there exists a pair of vertices $(A, B)$, such that every path from $A$ to $B$ contains edges in both colors $i$ and $j$ (thus $AB$ is not an edge). This is can be proved by considering the connected components when deleting all edges in color $i$, and grouping these connected components in two sets, such that every every edge "between" these two sets in the original graph is colored in $i$. Similarly for $j$, and the idea is to take $A$ and $B$ each to be common elements of two of the four sets described above. Then for each pair of colors $(i, j)$, assign the pair of vertices $(A, B)$, such that "the distance" between $A$ and $B$ is minimal. Now it should be proved (using the minimality) that every pair $(A, B)$ of vertices is assigned to at most one pair of colors. Therefore every pair of colors has been assigned exactly one such pair of vertices, and those pairs are different. So the pairs of vertices $(A, B)$, which are not connected with an edge, are at least the number of these pairs of vertices $(A, B)$, which are assigned to some pair of colors, i.e. at least $k(k-1)/2$. This proves the answer.

If dgrozev has got the question correct, I would say that the problem (as in #1) is very confusingly worded or translated; I would however also like to emphasize that this comment does not endorse any harsh feeling towards the problem proposer or the translator. Thank you dgrozev for helping us with knowing the correct question.

This problem seems uncannily similar to this problem from Turkey JBMO TST, 2015).

I think I did not understand the problem. According to the problem, is Lufhansa, for example, an airline or a company?

VicKmath7 wrote: Ok, so a sketch of the official solution. The answer is $N(N-1)/2-k(k-1)/2$. Lemma: For any pair of colors $(i, j)$, there exists a pair of vertices $(A, B)$, such that every path from $A$ to $B$ contains edges in both colors $i$ and $j$ (thus $AB$ is not an edge). This is can be proved by considering the connected components when deleting all edges in color $i$, and grouping these connected components in two sets, such that every every edge "between" these two sets in the original graph is colored in $i$. Similarly for $j$, and the idea is to take $A$ and $B$ each to be common elements of two of the four sets described above. Then for each pair of colors $(i, j)$, assign the pair of vertices $(A, B)$, such that "the distance" between $A$ and $B$ is minimal. Now it should be proved (using the minimality) that every pair $(A, B)$ of vertices is assigned to at most one pair of colors. Therefore every pair of colors has been assigned exactly one such pair of vertices, and those pairs are different. So the pairs of vertices $(A, B)$, which are not connected with an edge, are at least the number of these pairs of vertices $(A, B)$, which are assigned to some pair of colors, i.e. at least $k(k-1)/2$. This proves the answer. How do we know that if there is a path between the cities A and B, then there is no edge between them?!

Is it the case for any A and B? Or we choose such A and B pairs?

Represent the problem in term of graph $G$ whose vertices are cities, edges are airlines. We say that edge is painted in color $i$ if the respective airline belongs to airline number $i$. We claim that $G$ contains at most $\left(\begin{array}{c}N\\ 2\end{array}\right)-\left(\begin{array}{c}k\\ 2\end{array}\right)$ edges (and so the construction exists for $k<N$), what realizes: in clique $K_N$ pick vertices $V_1,V_2,...,V_k$ and remove all edges between them. Paint all edges from $V_i$ in color $i$ and all other edges paint arbitrary. Clearly this graph becomes disconnected after removing of all edges of some color. To prove the estimate it's suffice to show, that there are at least $\left(\begin{array}{c}k\\ 2\end{array}\right)$ anti-edges in $G.$ For every color $i$ let $A_i,B_i$ denotes sets of vertices in two unconnected with each other parts (they can be disconnected), obtained after removing of all edges colored $i$. For every pair $(i,j)$ we have $$A_i\cup B_i=A_j\cup B_j\implies (A_i\cap A_j)\cup (A_i\cap B_j)\neq \varnothing,\text{ }(B_i\cap A_j)\cup (B_i\cap B_j)\neq \varnothing,$$so in particular it's possible to assign a pair of vertices $(X,Y)$ (with minimal distance) for $(i,j)$, such that each path between them contains edges of both colors $i,j,$ and thus $XY$ is an anti-edge. Therefore it's suffice to prove the following Claim. $(X,Y)$ can't be assigned to more than one pair of colors. Proof. Assume the opposite. Consider one of pathes $XZ_1Z_2...Z_nY$ with minimal length, so $XZ_1$ is colored either $i$ or $j$ (or each path $Z_1-Y$ contains edges of both colors $i,j$ contradicting with minimality of distance), and similarly for $Z_nY$. Note that $(X,Y)$ can't be assigned to pair $(r,s)$ with both elements different from $i,j,$ because either each path $Z_1-Z_n$ contains edges of both colors $r,s.$ Thus $(X,Y)$ is assigned to pair $(i,r).$ By the same reason as above edges $XZ_1,Z_nY$ have one of color $i,r,$ so they are painted in $i.$ By minimality we may take pathes $X-Z_n-Z_1-Y$ without edges of color $i,$ which finally contradicts $\Box$