Question 169
Air Michael and Air Patrick operate direct flights connecting Belfast, Cork, Dublin, Galway, Limerick and Waterford. For each pair of cities exactly one of the airlines operates the route (in both directions) connecting the cities. Prove that there are four cities for which one of the airlines operates a round trip. (Note that a round trip of four cities $P, Q, R$ and $S$, is a journey that follows the path $P \to Q \to R \to S \to P$.)