IMO 1992 SL 4

Origin: CHN

Problem

Given nine points in space, no four of which are coplanar, find the minimal natural number n such that for any coloring with red or blue of n edges drawn between these nine points there always exists a triangle having all edges of the same color.

Solution

There are 36 possible edges in total. If not more than 3 edges are left undrawn, then we can choose 6 of the given 9 points no two of which are connected by an undrawn edge. These 6 points together with the edges between them form a two-colored complete graph, and thus by a well- known result there exists at least one monochromatic triangle. It follows that n \leq33. In order to show that n = 33, we shall give an example of a graph with 32 edges that does not contain a monochromatic triangle. Let us start with a complete graph C5 with 5 vertices. Its edges can be colored in two colors so that there is no monochromatic triangle (Fig. 1). Furthermore, given a graph H with k vertices without monochromatic triangles, we can add to it a new vertex, join it to all vertices of H except A, and color each edge BX in the same way as AX. The obtained graph obviously contains no monochromatic triangles. Applying this construction four times to the graph C5 we get an example like that of Fig. 2. Fig. 1 Fig. 2 Second solution. For simplicity, we call the colors red and blue. Let r(k, l) be the least positive integer r such that each complete r-graph whose edges are colored in red and blue contains either a complete red k-graph or a complete blue l-graph. Also, let t(n, k) be the greatest pos- sible number of edges in a graph with n vertices that does not contain a complete k-graph. These numbers exist by the theorems of Ramsey and Tur´an. Let us assume that r(k, l) < n. Every graph with n vertices and t(n, r(k, l)) +1 edges contains a complete subgraph with r(k, l) vertices, and this subgraph contains either a red complete k-graph or a blue complete l- graph. We claim that t(n, r(k, l)) + 1 is the smallest number of edges with the above property. By the definition of r(k, l) there exists a coloring of the complete graph H with r(k, l) −1 vertices in two colors such that no red complete k-graph or blue complete l-graph exists. Let cij be the color in

which the edge (i, j) of H is colored, 1 \leqi < j \leqr(k, l) −1. Consider a complete r(k, l)−1-partite graph G with n vertices and exactly t(n, r(k, l)) edges and denote its partitions by Pi, i = 1, . . . , r(k, l)−1. If we color each edge of H between Pi and Pj (j < i) in the color cij, we obviously obtain a graph with n vertices and t(n, r(k, l)) edges in two colors that contains neither a red complete k-graph nor a blue complete l-graph. Therefore the answer to our problem is t(9, r(3, 3)) + 1 = t(9, 6) + 1 = 33.