Between any two cities of country consisting of cities and country consisting of cities there is a unique direct two way flight organized by some airway company. For each given city there are at most different airway companies operating flights related to this city. Determine the maximum possible value of the integer such that no matter how these flights are arranged there are cities connected (not necessarily directly) only by the flights of some fixed airway company.
Solution
**The answer is .**
Let be a complete bipartite graph in which all vertices of a set with are connected to all vertices of with . We prove that there exists a monochromatic connected subgraph with vertices if edges of the graph are colored so that all edges incident to any given vertex are colored by at most colors. Indeed, let th color degree of a vertex be . For each connected pair of vertices , let us define where the edge connecting and is colored by the th color. The set of colors used for coloring of all edges incident to will be denoted by . The Cauchy-Schwarz inequality implies that
Therefore, by the pigeon hole principle there exist vertices with since .
Finally, we give an example with the greatest monochromatic connected component of size where only colors are used. Let us partition all vertices of and into sets and of sizes or and color all vertices between and into color where and . It can be readily seen that the maximal monochromatic connected component is of size .