Using technical language, the claim says that if the union of two equivalence relations is the set of all pairs, then so is at least one of the relations.
If A and B are two cities, let us write 1(AB) to say that company 1 offers a link between A and B, and similarly for 2(AB). Let us also write ~1(AB) and ~2(AB) for the negation of 1(AB) and 2(AB), respectively. In reading the following, it would help to draw a diagram. Suppose the conclusion of the claim is false, i.e., there exist cities A, B, C, D such that ~2(AB) and ~1(CD). Then 1(AB) and 2(CD). Suppose 1(AC) (the case when 2(AC) is similar). If 1(BD), then we have 1(CA), 1(AB), 1(BD), therefore, 1(CD), a contradiction. Therefore, 2(BD). What about AD? If 1(AD), then 1(CA) and 1(AD) imply 1(CD), a contradiction. If 2(AD), then 2(AD) and 2(DB) imply 2(AB), also a contradiction.