$n$ cities with two ways We have $n$ cities. Any two cities A and B of them, you can travel from A to B and B to A by car or by plane [But there is exactly one way, you can not travel A to B both by car or by plane]. There is at least one pair cities (A,B) so that you can travel from one to other by plane and there is at least one pair cities (C,D) so that you can travel from one to other by car. 
The question is that: Prove that we can remove one of such ways to travel: by car or by plane, so that for any two cities A,B. You can travel A to B by passing through at most two others cities C,D. [If you remove car ways, you can move from A to B by passing through cities C,D by plane only]. 
I am really have no ideas. Please give me some hints. Sorry for my bad English. 
 A: You cannot have $n \lt 3$ to satisfy the existence of a plane direct connection and a car direct connection. 
For $n=3$ you are going to have three direct connections, two of a particular type and one of the other. The first type of connection connects all the cities directly or indirectly. 
For $n \gt 3$, given A and B, take any two other cities.  Between these four cities there are six direct connections.  So at least three of the direct connections are of a particular type.  This particular type directly or indirectly connects all four cities, except when it forms a triangle between three of them and the other type provides direct connections between the fourth city and the other three.  Therefore in every case the four cities are linked directly or indirectly by a single type of connection.  This picture may help when there are at least three black direct connections:

So you can get between any two cities on a single type of connection, passing though at most two other cities.  
A: As I understand the question we have a complete graph $K_n$ whose edges are colored red and blue. It is claimed that we can remove all edges of a suitably chosen color and are left with a connected graph on $n$ vertices. (The statement is even stronger, but I won't go into that.)
The statement is true for $n=3$, and for all $n$ in the special case that one color is missing at the outset.  Assume that the statement is true for some $n\geq3$, and that we are given a colored $K_{n+1}$. If there are two edges with different colors you can find a vertex $v_0$ which is incident with two edges of different colors. Denote by $K_n'$ the colored complete graph resulting from removing $v_0$ and its incident edges, and apply the induction hypothesis to $K_n'$. If, say, the red edges can be removed from $K_n'$ leaving a connected graph, re-adjoin $v_0$, as well as the blue edges with $v_0$ as one endpoint, and obtain a connected "blue" graph on $n+1$ vertices.
