Nice problem. Here's my solution: We obviously restate the problem in graph-theoretic terms as follows: Restated problem wrote: Color each edge of the complete graph on $n$ vertices (i.e. $K_n$) by colors $C_1,C_2, \dots ,C_k$ such that Each edge is colored by only one color. For each color $C_i$, there exists some monochromatic path of color $C_i$ passing through all vertices of $K_n$. Find the maximum possible value of $k$ in terms of $n$. We claim that the answer is $k=\left \lfloor \frac{n}{2} \right \rfloor.$ Note that for the second condition to be true, there must exist atleast $n-1$ edges of color $C_i$ for all $i \in [k]$. Thus, we get $$k(n-1) \leq \binom{n}{2} \Rightarrow k \leq \frac{n}{2}$$Now, we show that the claimed value is indeed achievable. Consider $n$ even, and assume that $n=2m$. We prove the result for even $n$ by induction on $m$. For $m=1$, our claim is obvious. Suppose it is true for $m-1$. Consider the graph $K_{2m}$. Label the vertices as $v_1,v_2, \dots,v_{2m}$. According to the induction hypothesis, we can color the complete graph on vertices $v_1,v_2, \dots,v_{2m-2}$ with colors $C_1,C_2, \dots, C_{m-1}$ such that the given conditions are satisfied. Also these conditions mean that through each of these vertices, there passes an edge of color $C_i$. Now consider the vertices $v_{2m-1}$ and $v_{2m}$. Color the edges $v_{2m-1}v_{2j-1}$ and $v_{2m}v_{2j}$ with color $C_j$ for all $j \in [m-1]$. Also color the edges $v_{2m-1}v_{2j}$ and $v_{2m}v_{2j-1}$ with some new color $C_m$ for all $j \in [m]$. It is easy to see that this coloring satisfies the given conditions, and so we are done with the induction. For odd $n$, simply remove one vertex from the graph, and color the remaining complete graph with even number of vertices (which we can do as shown above). Now add that vertex back in, and color the edges coming out of that vertex with all the colors (in some order) present in our coloring of the even complete graph. Thus, we get the desired answer for odd $n$ also, and our claim is proved. Hence, done. $\blacksquare$

We see that the maximum for $n=4$ and $n=5$ is $2$,for $n=6$, we get this construction [asy][asy] /* Geogebra to Asymptote conversion, documentation at artofproblemsolving.com/Wiki go to User:Azjps/geogebra */ import graph; size(5cm); real labelscalefactor = 0.5; /* changes label-to-point distance */ pen dps = linewidth(0.7) + fontsize(10); defaultpen(dps); /* default pen style */ pen dotstyle = black; /* point style */ real xmin = -4.95655342757891, xmax = 4.725308261750672, ymin = -3.85913572707462, ymax = 4.274308714928064; /* image dimensions */ pen qqwuqq = rgb(0,0.39215686274509803,0); pen ffxfqq = rgb(1,0.4980392156862745,0); pen ccqqqq = rgb(0.8,0,0); /* draw figures */ draw(circle((0,0), 3), linewidth(1)); draw(circle((0,0), 3), linewidth(1)); draw(circle((0,0), 3), linewidth(1)); draw((-3,0)--(-1.499990713616107,2.59061174773431), linewidth(1.4) + qqwuqq); draw((-1.499990713616107,2.59061174773431)--(1.5,2.598076211353316), linewidth(1.4) + ffxfqq); draw((1.5,2.598076211353316)--(3,0), linewidth(1.4) + red); draw((3,0)--(1.5,-2.598076211353316), linewidth(1.4) + qqwuqq); draw((1.5,-2.598076211353316)--(-1.5,-2.598076211353316), linewidth(1.4) + ffxfqq); draw((-1.5,-2.598076211353316)--(-3,0), linewidth(1.4) + ccqqqq); draw((1.5,2.598076211353316)--(-1.5,-2.598076211353316), linewidth(1.4) + qqwuqq); draw((-1.499990713616107,2.59061174773431)--(1.5,-2.598076211353316), linewidth(1.4) + red); draw((-3,0)--(3,0), linewidth(1.4) + ffxfqq); draw((1.5,2.598076211353316)--(1.5,-2.598076211353316), linewidth(1.4) + red); draw((1.5,-2.598076211353316)--(-3,0), linewidth(1.4) + ffxfqq); draw((-3,0)--(1.5,2.598076211353316), linewidth(1.4) + qqwuqq); draw((-1.499990713616107,2.59061174773431)--(-1.5,-2.598076211353316), linewidth(1.4) + red); draw((-1.5,-2.598076211353316)--(3,0), linewidth(1.4) + qqwuqq); draw((3,0)--(-1.499990713616107,2.59061174773431), linewidth(1.4) + ffxfqq); /* dots and labels */ dot((3,0),dotstyle); dot((1.5,2.598076211353316),linewidth(4pt) + dotstyle); dot((1.5,-2.598076211353316),linewidth(4pt) + dotstyle); dot((-1.499990713616107,2.59061174773431),dotstyle); dot((-1.5,-2.598076211353316),linewidth(4pt) + dotstyle); dot((-3,0),dotstyle); clip((xmin,ymin)--(xmin,ymax)--(xmax,ymax)--(xmax,ymin)--cycle); /* end of picture */ [/asy][/asy] where each color represents a airline. Since we are going to take a look at a graph, we place all the cities on a circle with radius $1$ and place them in the fashion such that they create a regular $n$-gon. Our goal is to minimize as much as possible. That is to create a path with the least amount of segments. So we see that the minimum is $n-1$ segments.From here we have the following inequality: $$(n-1)k \leq \frac{n(n-3)}{2}+n=\frac{n(n-1)}{2}$$from here we see that $k \leq \frac{n}{2}$. Since $k$ is a natural number, we have that the maximum is $k=\left \lfloor \frac{n}{2} \right \rfloor$. The construction: Choose one vertex and then zig-zag to the next one, and we do this for the next consecutive $\left\lfloor \frac{n}{2} \right \rfloor$ vertices.

I wonder how many words were used for a simple question: What is the maximum number of edge-disjoint spanning trees in a complete graph with $n$ vertices?

By checking small cases $n=1,2,3,4,5,6$ it is pretty easy to guess that the answer is $k=\lfloor \frac{n}{2} \rfloor$. Let's prove it The maximality of $\lfloor\frac{n}{2}\rfloor$. A connected graph of $n$ vertices must contain at least $n-1$ edges. So there are at least $n-1$ edges of each color. From this we get the inequality: $$\dfrac{n(n-1)}{2}\geq k(n-1)\Longrightarrow \dfrac{n}{2}\geq k$$since $k$ is a positive integer, we have $k\leq \lfloor\frac{n}{2}\rfloor$ Construction for even n. We will prove by induction on $m$ that the vertices of a complete graph with $2m$ vertices can be colored in $m$ colors in the desired way. The base case $m=1$ is trivial. Take a graph with $2m+2$ vertices and ignore two of its vertices $A$ and $B$. By induction hypothesis, color the edges of the left graph in $m$ colors. After coloring, divide the vertices of the graph into two sets $S$ and $T$, each containing $m$ vertices. Now, return $A$ and $B$. Connect $A$ with all the vertices of set $S$ with all of the $m$ colors. Connect $B$ with all the vertices of set $T$ with all the $m$ colors. So far, we have graph with edges of $m$ colors, each color of which forms a connected graph. Now, let's add a new color. Connect $A$ with all the vertices of set $T$ by new $(m+1)$'s color. Connect $B$ with all the vertices of set $S$ by new $(m+1)$'s. Finally, connect $A$ and $B$ with the new color. At the end, we have the desired construction. Construction for odd n. Take a graph on $2m+1$ vertices $(m\geq 1)$. Ignore a vertex $A$ and color the left graph in $m$ colors. After that, connect $A$ randomly with all the vertices, such that among the new edges, each color presents. This would be the desired configuration.