So for $n=6$ by the well-known argument, we have a monochrome triangle, so that doesn't work, and for $n=4$ a working construction is easy to find (connect vertex pairs {1,2}, {1,3}, {3,4} with red, and the rest blue). The question is, what about $n=5$? Well, if any vertex is connected to 3 others by lines of the same color, we're done (since if any of these three are connected by that same color as well, we have a triangle, if none, they themselves form a monochromatic triangle). Thus, if we have a counter-example, each vertex has two edges of each color from it. WLOG, connect 1 to 2 and 3 by red, 4 and 5 by blue. 2-3 is b, and 4-5 must be red, else we have triangles. Then, 2 is connected to one of 4,5 by blue, and the other by red (since it already has one red and one blue edge), WLOG connect it to 4 by blue, 5 by red. 3-5 must be blue, or else 1-2-5-3 form a red 4-cycle, and then 3,4 is blue to preserve the 2 of each color at 2. But then 2,3,4 is a blue cycle, so 5 doesn't work and 4 is the maximum.

In fact, this problem is exactly lemma 20.1 in Problems From the Book. Lemma 20.1 states: Every coloring in 2 colors of a complete 6-graph contains a monochromatic triangle. The only coloring of two colors in a complete 5-graph that does not have monochromatic triangles has the form: there exists a pentagon with diagonals blue and sides red. It's surprising that such a well-known result could show up on a contest...

Using a result like that is overkill. It's not surprising that a problem on the easy side like this one has appeared in a generalized form before. The problem is basically asking when $K_n$'s edges can be partitioned into two acyclic graphs. An acyclic graph on $n$ vertices can have at most $n-1$ edges, so there are at most $2(n-1)$ edges. On the other hand $K_n$ has $\frac{n(n-1)}{2}$ edges, so $n \leq 4$. Get the easy construction for $K_4$ and that's it.

Similarly, for $3$ colors we need three acyclic graphs, thus $\frac {n(n-1)} {2} \leq 3(n-1)$, whence $n\leq 6$. A model for a $K_6$ of vertices $\{1,2,3,4,5,6\}$ is given by the three paths $123456, 246135, 362514$. Is it true that, for $k$ colors, needing $\frac {n(n-1)} {2} \leq k(n-1)$, hence $n\leq 2k$, the graph $K_{2k}$ can be partitioned into $k$ paths of length $2k-1$ each? or else in some other way into $k$ spanning trees ? This result should be known, I guess ... EDIT. Indeed, it is proved that a $K_{2k}$ has a decomposition into $k$ Hamiltonian paths. Together with the above necessary condition $n\leq 2k$, we have a complete answer.

mavropnevma wrote: Is it true that, for $k$ colors, needing $\frac {n(n-1)} {2} \leq k(n-1)$, hence $n\leq 2k$, the graph $K_{2k}$ can be partitioned into $k$ paths of length $2k-1$ each? or else in some other way into $k$ spanning trees ? This result should be known, I guess ... Slightly less specific, it's easy to prove by induction there exist trees such that their union is the graph (i.e. a construction for 2k cities and k airlines), by a basic induction. Consider the n trees of length 2n-1 for the 2n case, and then for 2n+2 case, we have n+1 trees of length 2n+1; to make these just attach vertices 2n+1 and 2n+2 to vertex 1 in the tree for airline 1, attach them to vertex 2 in the tree for airline 2, etc up to n. Now we just need to connect vertices 2n+1 and 2n+2 to each other as well as to vertices n+1,...,2n -- just draw those in. Obviously all of these new "trees" are in fact still trees, since we can't have accidentally introduced a cycle. So the answer is in the general case of $k$ airlines is indeed $2k$, though I haven't found a construction consisting solely of paths or spanning trees yet.

The condition is saying that there is a graph $G$ on $n$ vertices such that it and its complement are both forests. We have $|E|=|V|-k$ for a forest ($k$ is the number of connected components). Therefore, we have that $e<n$ and $\binom{n}{2}-e<n$ where $e$ is the number of edges of $G$, so $\binom{n}{2}<2n$, so $n\le \boxed{4}$. For $n=4$, consider a path graph.

We are given that $K_n$ can be partitioned into two forests. Since forests are 2-colorable, $K_n$ is $2 \cdot 2$-colorable, so $n \le 4$.

This is just saying the largest possible number of vertices with no monochromatic cycle. We claim the answer is 4. This can be achieved by making the "C" shape red and the rest of the graph blue. Consider the graph $B$ consisting of all the blue edges, and the graph $R$ consisting of all the red edges. Since each graph does not have a cycle, $B$ and $R$ both have at most $n-1$ edges. Since they have a total of ${n\choose 2}$ edges, we have $${n\choose 2}\leq 2(n-1)\rightarrow n\leq 4,$$hence done.

Consider a graph $K_n$ with each edge colored red and blue. By Pigeonhole, at least $\left\lceil \frac{\binom n2}{2} \right\rceil$ edges of some color, say red. The maximal number of edges of a graph on $n$ vertices with no cycles is $n-1$, or a tree, so \[\left\lceil \frac{\binom n2}{2} \right\rceil \leq n-1 \implies n \leq \boxed{4},\]which is easily constructable.

Look at this in terms of graphs. The country is like a complete graph on $n$ vertices and the airlines are like coloring each edge in one of two colors - Blue or Red. So, what we need is the maximum value $n$ for which it is possible for the mathematician to take a cycle composed of only black or only white edges. We claim that the answer is $4$. Note that, if we partition the edges into two groups as red and blue, each group must be acyclic (or else it is possible for the mathematician to pass through only edges of one color and return to where she started). But, we know that a tree on at most $n$ vertices has at most $n-1$ edges. Thus, each of these groups can have at most $n-1$ edges. On the other hand $K_n$ clear has $\binom{n}{2}$ edges and thus, \[\frac{n(n-1)}{2} \leq 2(n-1)\]from which we conclude that $n\leq 4$ as desired. Simply consider the following graph as a construction for $n=4$,

Attachments:

The answer is $\boxed{n=4}$. Consider a graph $K_n$ with each edge colored red or blue. Neither monochromatic graph has a cycle, so each one has at most $n-1$ edges. Hence, \[\binom{n}{2} \le 2(n-1) \implies n \le 4,\] which is easily constructed.

If $n \geq 6$ there are three edges coming tru a single vertex in the same color, because of Dirihlet. Now the edges connecting the edges with the same color, should be colored in the other color leading to getting a monochromatic triangle - impossible. If n = 5, after bruteforcing the cases there is either a monochromatic triangle or pentagon, contradiction. For n = 4, the coloring is easy: if $K_4$ is square-like we color 3 of its sides with red and the other edges with blue $\Rightarrow$ $n \geq 5$, doesn't work and we show n = 4 work $\Rightarrow$ n = 4.