BALKAN-SL 2007 C3

Three travel companies provide transportation between $n$ cities, such that each connection between a pair of cities is covered by one company only. Prove that, for $n \geq 11$, there must exist a round-trip through some four cities, using the services of a same company, while for $n < 11$ this is not anymore necessarily true.

Dan Schwarz