The answer is $n = 2015$. 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 be identically colored and the remaining edges be differently colored. The conditions are held and $n = 2013 - 99 + 1 = 2015$.

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 $b - |Y_B| + p$ vertices other than $u$. Similarly, $q$ trees connecting $v$ to $A-Y$ 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_B| + |Y_A| = |Y| - 2$ the total color loss is $a + b = 98$. Thus, the total number of colors is at most $2013 - 98 = 1915$. Done.