Translation into graph language: A complete graph contains 10 vertices and all its edges colored either in one of the two possible colors,red or black,or in both colors. We need to prove that one can choose edges of either red or black color,such that this subgraph contains two connected components,each with odd number of vertices. If got it correctly,the needed subgraph may not contain all vertices,right?Can edge be colored in both colors? Does round trip means that all vertices can be connected by using only one color,or it just means that edges are not ordered?

Maybe one should note if there is a direct service from $ x$ to $ y$ and $ x \neq y,$ then this airline also offers this direct service from location $ y$ to $ x.$ Try to prove the following statement: Colour the edges of a complete graph $ K_m$ with $ n$ colours and if we have that $ m > 2^n, n \geq 1,$ then within $ K_m$ there exists a monochromatic circle of odd length. A subgraph $ G'$ of some graph $ G$ is called monochromatic if all its edges have the same colour. Use induction.

By way of contradiction, suppose any two odd cycles of the same color intersect. Since $10>R(3,3)$ there is a monochromatic triangle, let us say it is black and call it $T$. Consider the remaining $7$ vertices, there is no odd black cycle in here, so the black part of the graph is bipartite and therefore there are at least two complete red subgraphs, the possibilites for the sizes are: $(1,6),(2,5),(3,4)$ in all of the cases except $2,5$ It is clear that there is going to be two disjoint red triangles. So we only have to check the case in which we have a black triangle $T$, a red $K_2$ and a red $K_5$ (and they are all mutually disjoint). Pick vertices $t_1$ and $t_2$ in $T$, notice that if any of them has at least two red edges towards the red $K_5$ then we can obtain two disjoint red triangles. So each of them has at east $4$ black edges towards the $K_5$. Therefore there must be a vertex $x$ in the $K_5$ so that $t_1,t_2,x$ forms a black triangle. Now let $t_3$ be the remaining vertex in $T$. It must send at least one black edge toward the $K_2$. Call the other endpoint of this edge $y$. As before, notice at least $4$ of the edges from $y$ to the $K_5$ and from $t_3$ to the $K_5$ must be black. Therefore there is a vertex $z$ in the $K_5$ (other than $x$) so that $t_3,y,z$ forms another black triangle.

Can someone remove the part about $1990>2^{10}$ in the title? It kinda gives the problem away

How does it give the problem away, what does $1990$ have to do with the problem statement? Also, I thought what we had to prove is that there are two disjoint odd cycles of the same color. Is this not the case?

Oops. The title made me think of a similar problem: 1990 cities are served by ten airlines, such that between any two cities some airline offers a two-way flight between them. Show that one of the airlines can offer a round-trip with an odd number of cities.

oh yeah, that one is very nice. I think Ori also confused it with this one

orl wrote: Ten localities are served by two international airlines such that there exists a direct service (without stops) between any two of these localities and all airline schedules offer round-trip service between the cities they serve. Prove that at least one of the airlines can offer two disjoint round trips each containing an odd number of landings. Graph theoretic interpretation : Take a $K_10$ graph (10 vertices and each pair of vertices has an edge between them) color each edge either blue or red (these represent the airlines respectively). We wish to show that there exist 2 disjoint odd monochromatic cycles. Solution: (slightly similar to @Gamamal) We know that since $10>R(3,3)=6$ (where $R$ refers to ramsey numbers), there must exist a monochromatic triangle. WLOG let it be blue colored. Now, delete these three vertices from the graph. We now wish to show that there exists either an odd blue cycle or $2$ disjoint odd red cycles on the remaining $K_7$ graph. If there exists a blue odd cycle, we are done, so assume not. Now we know that $K_7$ is not bipartite so there must exist an odd cycle and since $7>R(3,3)=6$, There infact exist multiple red triangles . Now delete $3$ vertices of a red cycle such that in the resulting graph all the blue edges are incident to a single vertex, which is clearly possible otherwise if in all the sub-graphs of $4$ vertices there are two blue edges that are not adjacent, it is possible to show that we must have multiple edges that are blue and that there does exist a blue triangle, which is a contradiction to our assumptions.

Finally we now have a $K_4$ graph which must have an odd cycle (not necessarily monochromatic) since complete graphs are non-bipartite. But note that the number of blue edges must be $\leq 3$ by Turan's theorem since there doesn't exist any blue triangle here (by assumption). Now there are three cases (number of blue edges $=1,2,3$) and in each one it is easy to verify (by constructing edges WLOG) that there infact does exist a red triangle and we are done.