Click to reveal hidden text

give solution!.

Official Problem: Some pairs of cities of a country consisting of $100$ cities are connected by $2013$ round trip flights operated by $n$ air companies. There are at least two cities such that one is not reachable from other one by one or two flights. Given that for any pair of cities there is an air company connecting these two cities by direct or indirect flights, find the maximal possible value of $n$. Official Solution: The answer is $n=1915$. The solution will be given in terms of graph theory: vertices are cities, edges corresponding to flights will be identically colored if they belong to the same air company. Let all edges of a tree connecting all $100$ vertices are identically colored and the remaining edges are differently colored. The conditions are held and $n=2013-99+1=1915$. Now we prove that there are at most $1915$ colors. Consider a coloring of $G$ with maximal number of colors. Then Identically colored edges form a connected tree. Indeed, if there is a monochromatic cycle we can recolor one of its edges in a new color and increase the number of colors, if two identically colored trees are not connected then we can recolor one of these trees in a new color and thereby increase the number of colors. Two trees can not have more than $2$ intersections. Indeed, if there are more than two intersections the union of two trees includes at least two cycles and we can recolor these two trees identically and after that recolor one edge in each cycle in new colors and thereby increase the number of colors. W.l.o.g. we can suppose that if two trees intersect at two vertices then both vertices are endpoints (vertices of degree one) of these trees. Indeed if one of intersection vertices is not an endpoint there is a cycle; we can recolor these two trees identically and after that recolor one edge in a cycle by new color thereby the number of colors will not change. Consider vertices $u$ and $v$ located at distance at least $3$. Let $X$ be the set of vertices of a tree connecting $u$ and $v$ and $Y=X-\{u,v\}$. $|Y|$ denotes the number of vertices in $Y$. Let $A$ be the set of all neighbor vertices of $u$ and $B=G-u-v-A$. $|X|$ denotes the number of elements in $X$. Let $|a|=a$, $|B|=b$, $|Y\cap A|=Y_A$, $|Y\cap B| = Y_B$. Let $u$ be connected to vertices of $B-Y$ by some trees $T_1, \dots, T_p$ and $Z_1, \dots, Z_p$ be their vertices, $X_i \cap X_j = \emptyset$ since different trees already have intersection in $u$. Therefore to each tree $T_i$ $i=1,\dots, p$ we can assign a different vertex in $A$. Therefore, $p$ trees $T_1, \dots, T_p$ contain at least $a-|Y_A| + q$ vertices other than $v$. If a tree contains $d$ vertices other than its root $d$ edges are identically colored and color loss $d-1$. Thus, the total color loss will be $b-|Y_B| + p - p + a - |Y_A| + q-q + |Y|-2$. Since $|Y_A| + |Y_B| = |Y| - 2$ the total color loss is $a+b=98$. Thus, the total number of colors is at most $2013-98=1915$. Done.

The answer is $\boxed{1915}.$ This is attained by taking a spanning tree to be one company and then all the other edges to be the other companies. Let's now show that this is maximal. Let $v, w$ be the two vertices which are not connected with a path of length $1$ or $2.$ Let $S_v, S_w, S_x$ be the set of the other $98$ vertices which are connected to $v$, connected to $w$, and connected to none of $v, w$, respectively. Observe that $S_v, S_w, S_x$ are pairwise disjoint by the condition. Let the companies have $e_1, e_2, \cdots, e_t$ edges respectively. Observe that $\sum e_i = 2013.$ Therefore, if we were to show that $\sum (e_i - 1) \ge 98$, then we'd be done. First of all, notice that if there is a company so that its flights don't comprise a connected graph, we can just split it into two companies to decrease $\sum (e_i -1)$ (while clearly preserving the conditions of the problem). Hence, WLOG assume that the flights of all companies are connected. Call a company $\mathbf{special}$ if either it services both $v$ and something in $s_w \cup s_x$ or it contains both $w$ and something in $s_v \cup s_x.$ Call a company $\mathbf{doubly}$ $\mathbf{special}$ if it services $v, w$ and cities in $s_w \cup s_x, s_v \cup s_x.$ Let $C_1, C_2, C_3, \cdots, C_n$ be the special companies, and let them have $v_1, v_2, \cdots, v_n$ vertices respectively. Observe that $C_i$ has at least $v_i - 1$ edges by connectivity, and so to show $\sum (e_i - 1) \ge 98$ we just need $\sum (v_j - 2) \ge 98.$ Let's show this as follows. For a company $C_j$, we will associate it to a set of $v_j - 2$ vertices as follows. If it is doubly special, simply associate it to its vertices which are not $v, w.$ If it is doubly special, we consider two cases. If it contains $v$ and some vertex $v'$ in $s_w \cup s_x$, then it must contain a neighbor $v_1$ of $v$ (since there is a path from $v$ to $v'$ using this company). Then, associate it to its vertices which are not $v, v_1$. If it contains $w$ and some vertex $w'$ in $s_v \cup s_x$, do a similar thing by excluding $w$ one of its neighbors. We claim that these sets of vertices must cover all of $s_v \cup s_w \cup s_x.$ Indeed, this is easy to show. Suppose that there is a vertex $y \in s_v \cup s_w \cup s_x.$ If $y \in s_v \cup s_x$, then there must exist a company connecting $y$ and $w$, say $C_j.$ If it is doubly special, then $C_j$'s associated vertex set contains $y$ because it's not $v$ or $w.$ If it is singly special, then its associated vertex set contains $y$ because its not $w$ or a neighbor of $w.$ In either case, $y$ is contained in $C_j$'s associated vertex set. If $y \in s_w \cup s_x$ the argument is analogous. Hence, we've shown that these vertex sets cover all $98$ vertices which are not $v$ or $w$, and so because their cardinalities are $v_1-2, v_2-2, \cdots, v_n - 2$, we have $\sum (v_j-2) \ge 98$ and we're done. $\square$