Assume that all edges of a complete graph $K_n$ are colored in $k$ colors. We want to choose $m$ colors so that the graph formed by edges of chosen colors is connected. It is always possible if $m\geq k/2$ (partition all colors onto two groups of at most $m$ colors, it is impossible that both groups form disconnected graph). If $k=2m+1$ this is already not always possible for large enough $n$. Namely, if $n=\binom{2m+1}{m}$ it may appear that for any $m$subset $I$ of colors there exists a vertex $v_I$ such that no edge ended in $v$ has color from $I$. The specific question is do we really need such a large $n$? Say, if $n$ grows in $m$ subexponentially, may we choose $m$ colors which form a connected subgraph?

$\begingroup$ I should think so. Not an argument, but the following might become one. Suppose one tries to select m colors from a colored graph, say by choosing the m most popular colors. If it fails, the complement contains a connected and complete bipartite graph, which presumably has many more edges because n is so large. This should at least give bounds on n. Gerhard "Can't Count: Not Enough Coffee" Paseman, 2015.03.05 $\endgroup$ – Gerhard Paseman Mar 5 '15 at 18:04
Well, the argument below proves much weaker statement that you've asked for: if $n$ is subexponential in $\sqrt{m}$ (more precisely if I'm not mistaken, if $n<\exp(c m/\sqrt{k})$, where $c$ is a constant). But it is clearly suboptimal, so quite probably one can improve it.
The idea is to use a greedy algorithm. That is, assume that you are in a situation $(n,k,m)$, find a color that minimizes the number $n'$ of connected components using this color only. Pick this color and consider the connected components as new vertices (for instance, picking a vertex in each component and forgetting the rest); then, you are in a situation $(n',k1,m1)$. Now, if the passage from $n$ to $n'$ reduces the number of vertices sufficiently fast, you will be done (even though the $m1:k1$ ratio becomes less and less favorable).
Next remark is that if you pick a color at random, the mean size of a connected component of a given vertex is sufficiently large: it is at least $1+\frac{n1}{k}$, as this is the expectation of the size of the radius one neighborhood. And, if $n$ is large, it is a lot. So the least possible $n'$ should be noticeably smaller, than~$n$.
If one can get the $n'<0.99n$ in the above argument (say, assuming $m>k/10$), that would lead to a positive answer to your initial question. The argument below leads to a weaker statement. That is: average size of the connected component of a given vertex is $1+\frac{n1}{k}$. Hence, the sum of all such sizes over all the vertices, in average, is at least $n(1+\frac{n1}{k})$. Hence, there exists a color, for which such a sum is at least $n(1+\frac{n1}{k})$. On the other hand, this sum equals to $\sum s_i^2$, where $s_i$ are the sizes of the connected components (each component is counted as many times, as is its size). Hence, we have $$ \sum_i s_i^2 \ge n\left(1+\frac{n1}{k}\right). $$ Let $n'$ be the number of connected components, and denote $\delta:=nn'+1$. For a given $n'=n(\delta1)$ of positive integer summands $s_i$ with $\sum s_i=n$, the sum $\sum_i s_i^2$ is maximized if all of the components but one consist of one vertex, and the last one consists of $\delta$ vertices. In this case, this sum is equal to $\delta^2+(n\delta)\cdot 1^2$. Hence, $$ n\delta+ \delta^2\ge n+ \frac{n(n1)}{k}, $$ and thus $$ \delta(\delta1)\ge \frac{n(n1)}{k}. $$
This leads to $\delta\ge \frac{n}{\sqrt{k}}$, and hence $$ n'= n(\delta1) = n\left(1\frac{1}{\sqrt{k}}+\frac{1}{n}\right). $$
Well, the $1/n$ in the right hand side is almost neglectable, and taking $m$ iterations will reduce to $1$ the number of connected components, if we start with at most $$ \sim \exp \left(\sum_{j=km+1}^k \frac{1}{\sqrt{j}}\right)\ge \exp \left(\frac{m}{\sqrt{k}}\right). $$

$\begingroup$ I am afraid that greedy algorithm as is does not provide any better bound, since it may easily happen that each color has about $n(1\delta)$ components for $\delta=O(1/\sqrt{k})$: partition all vertices onto blocks of $\delta n$ vertices and for any pair of blocs A, B color all edges between A,B in a special color. $\endgroup$ – Fedor Petrov Mar 6 '15 at 13:03