Any solution?

$k=1007$. Let's put $m$ instead of $2015$ and prove that the maximal value of $k$ is $\lfloor m/2\rfloor$. So, we have a complete graph with $n=10^m$ vertices; its edges are colored with $m$ colors, and we want to find the maximal value of $k$, such that we always can delete some $k$ colors leaving the graph still connected. Choose arbitrarily $k$ colors. Let $G_1$ be the graph consisting of the edges colored with that $k$ colors and $G_2$ be the graph consisting of the edges colored with the rest $m-k$ colors. Thus, $G_2$ is the complement of $G_1$. It is easily checked that if one of $G_1,G_2$, say $G_1$, is not connected then the other - $G_2$ must be connected. Indeed, suppose $G_1$ is disconnected and let $C_1,C_2,\dots,C_r\,,\,r>1$ be the connected components of $G_1$. Then any edge $uv$ where $u\in C_i\,,\,v\in C_j\,,\,i\neq j$ must be in $G_2$ , hence $G_2$ is connected. It follows, we can always delete at least $\lfloor m/2\rfloor$ colors and get still a connected graph. To prove it's the most we can get, it's enough to construct a coloring with $m$ colors of a complete graph (with not too many vertices), such that removing any $\lfloor m/2\rfloor+1$ colors will make the graph disconnected. The construction is as follows. Let $V_1$ be a set of $k:=\lfloor m/2\rfloor+1$ vertices and $V_2$ a set of $\binom{m}{k}$ vertices. Consider the complete graph $G$ on the set of vertices $V := V_1\cup V_2$. We map every set $S$ of $k$ distinct colors, among the given $m$ , to a vertex $v\in V_2$ and color the edges between $v$ and the vertices of $V_1$ using each color in $S$ exactly once. We color arbitrary the edges between the vertices in $V_1$ . It remains to color the edges in $V_2$. Fix some $u,v\in V_2$ and let $C(u)$ resp. $C(v)$ be the sets of colors the edges connecting $u$ to $V_1$, resp. $v$ to $V_1$ are colored with. Since $|C(u)|+|C(v)|=k+k>m$ it follows $C(u)\cap C(v)\neq \emptyset$. We color the edge $uv$ with a color that is present in both $C(u)$ and $C(v)$. Proceeding that way, it preserves the set of colors of the edges incident to any vertex of $V_2$. So, after coloring all edges of $G$, for any combination of $k$ colors among the given $m$, there exists a vertex in $G$ having exactly that set of colors of edges incident with it. That's why, if we delete any $k$ colors, there will be a vertex that will become isolated. The number of the vertices of $G$ are $k+\binom{m}{k}<\lfloor m/2\rfloor +1 +2^m<10^m$. EDIT: The constructed above graph $G$ has less than $10^m$ vertices, but of course we can add some additional "dummy" ones and paint the additional edges so that to preserve the set of colors incident to each vertex in $V_2$.