6. A country has $n(n \geqslant 3)$ cities and two airlines. There is exactly one two-way flight between every pair of cities, and this two-way flight is operated exclusively by one of the airlines. A female mathematician wants to start from a city, pass through at least two other cities (each city is visited only once), and finally return to the starting city. She finds that no matter which starting city and intermediate cities she chooses, she cannot complete her journey using only one airline. Find the maximum value of $n$.
(Liang Yingde, problem contributor)
6. Solution 1 Consider each city as a vertex, each flight route as an edge, and each airline as a color. Then, the country's flight network can be seen as a complete graph with $n$ vertices whose edges are colored with two colors.

From the condition, we know that any cycle contains edges of both colors, meaning that the subgraph formed by edges of the same color has no cycles.

By a well-known conclusion, the number of edges in a simple graph without cycles is less than the number of vertices. Therefore, the number of edges of each color does not exceed $n-1$. This indicates that the total number of edges does not exceed $2(n-1)$.

On the other hand, the number of edges in a complete graph with $n$ vertices is $\frac{n(n-1)}{2}$.
Therefore, $\frac{n(n-1)}{2} \leqslant 2(n-1) \Rightarrow n \leqslant 4$.
When $n=4$, let the four cities be $A$, $B$, $C$, and $D$. If the routes $A B$, $B C$, and $C D$ are operated by the first airline, and the routes $A C$, $A D$, and $B D$ are operated by the second airline, it is easy to see that the routes operated by each airline form a chain and do not contain any cycles, i.e., this scenario satisfies the conditions of the problem.
In summary, the maximum value of $n$ is 4.
Solution 2 From the same reasoning as in Solution 1, we know that the subgraph formed by edges of the same color has no cycles.

By a well-known conclusion, a complete graph with six vertices, when colored with two colors, must contain a monochromatic triangle, i.e., a monochromatic cycle.
Therefore, $n \leqslant 5$.
We now prove: $n \neq 5$.
If not, let the five vertices be $A$, $B$, $C$, $D$, and $E$. Consider the four edges extending from vertex $A$. If at least three of these edges are the same color (e.g., $A B$, $A C$, $A D$ are the same color), then among $B C$, $B D$, and $C D$, there will be an edge of the same color as the aforementioned three edges, leading to a monochromatic triangle, which is a contradiction. If $B C$, $B D$, and $C D$ are all different colors from $A B$, $A C$, and $A D$, they will form a monochromatic triangle, which is a contradiction. If each vertex has exactly two edges of the same color, it is easy to see that the graph contains a Hamiltonian cycle, which is a contradiction.
Therefore, $n \leqslant 4$.
The rest follows the same reasoning as in Solution 1, showing that $n$ can be 4.
Hence, the maximum value of $n$ is 4.