Problem 1583

The problem can be reinterpreted in graph theory terminology as the following: If $K_6$ is edge-coloured with two colours then there exists a monochromatic $C_4$ (cycle of length 4). As $K_6$ has 15 edges one of the colours, say red, must appear at least 8 times. Suppose the other colour is blue. Consider all the induced graphs on 4 vertices which have 6 edges. They cannot all have the same number of edges of the two colours as then the same would be true of $K_6$. Thus there are four vertices $P, Q, R, S$ defining a $K_4$ which has 4, 5, or 6 red edges. In the case that there are 5 or 6 red edges it is easy to find a red $C_4$. If the four red edges form a $C_4$ we are done. If not, we have $PQ$, $QR$, $RP$, $PS$ red and $QS$, $RS$ blue. There are at least 4 more red edges in our $K_6$. Thus one of the remaining vertices must be connected to $P, Q, R, S$ by at least two red edges. In all cases a red $C_4$ appears except in the case that $TP$ and $TS$ are red and $TQ$ and $TR$ are blue. But now $TRSQ$ is a blue $C_4$. This completes the proof.

Alternative solution with less graph theory:

There are $\binom{6}{2} = 15$ routes between the 6 cities. Thus one airline, say Air Michael, must run at least 8 of the routes.

Choose any four cities. There are $\binom{4}{2} = 6$ routes between these four cities. If for all choices of four cities the routes were divided 3-3 between Air Michael and Air Patrick then they would also have the same number of routes overall which is impossible since 15 is odd. Thus for one choice of four cities, Air Michael must run 4 or more of the routes. If they run five or six of the routes, there will be a round trip. If they run four and these form a round trip we are also done. The other possibility is they run four routes which do not form a round trip. Calling these four cities $P, Q, R, S$ we can assume that Air Michael runs routes $PQ$, $PR$, $PS$ and $QR$. Air Michael runs at least four more routes, at least 3 of the routes from $P, Q, R, S$ to the other two cities $T$ and $U$. One of these cities, say $T$ must have two or more routes to $P, Q, R, S$. If there are three routes then a round trip occurs. The only two Air Michael routes which will not produce a round trip are $TP$ and $TS$. But then $QSRT$ will be a round trip run by Air Patrick.