IMO 1990 SL 22

Origin: ROM

Problem

Ten localities are served by two international airlines such that there exists a direct service (without stops) between any two of these localities and all airline schedules offer round-trip service between the cities they serve. Prove that at least one of the airlines can offer two disjoint round trips each containing an odd number of landings.

Solution

We can assume without loss of generality that each connection is ser- viced by only one airline and the problem reduces to finding two disjoint monochromatic cycles of the same color and of odd length on a complete graph of 10 points colored by two colors. We use the following two stan- dard lemmas: Lemma 1. Given a complete graph on six points whose edges are colored with two colors there exists a monochromatic triangle. Proof. Let us denote the vertices by c1, c2, c3, c4, c5, c6. By the pigeonhole principle at least three vertices out of c1, say c2, c3, c4, are of the same color, let us call it red. Assuming that at least one of the edges connecting points c2, c3, c4 is red, the connected points along with c1 form a red triangle. Otherwise, edges connecting c2, c3, c4 are all of the opposite color, let us call it blue, and hence in all cases we have a monochromatic triangle. Lemma 2. Given a complete graph on five points whose edges are colored two colors there exists a monochromatic triangle or a monochromatic cycle of length five. Proof. Let us denote the vertices by c1, c2, c3, c4, c5. Assume that out of a point ci three vertices are of the same color. We can then proceed as in Lemma 1 to obtain a monochromatic triangle. Otherwise, each

point is connected to other points with exactly two red and two blue vertices. Hence, we obtain monochromatic cycles starting from a single point and moving along the edges of the same color. Since each cycle must be of length at least three (i.e., we cannot have more than one cycle of one color), it follows that for both red and blue we must have one cycle of length five of that color. We now apply the lemmas. Let us denote the vertices by c1, c2, . . . , c10. We apply Lemma 1 to vertices c1, . . . , c6 to obtain a monochromatic triangle. Out of the seven remaining vertices we select 6 and again apply Lemma 1 to obtain another monochromatic triangle. If they are of the same color, we are done. Otherwise, out of the nine edges connecting the two triangles of opposite color at least 5 are of the same color, we can assume blue w.l.o.g., and hence a vertex of a red triangle must contain at least two blue edges whose endpoints are connected with a blue edge. Hence there exist two triangles of different colors joined at a vertex. These take up five points. Applying Lemma 2 on the five remaining points, we obtain a monochromatic cycle of odd length that is of the same color as one of the two joined triangles and disjoint from both of them.