4. $(\mathbf{C H N} 3)^{\mathrm{IMO}}$ 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.
4. 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 \leq 33 \). 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 \( C_{5} \) with 5 vertices. Its edges can be colored in two colors so that there is no monochromatic triangle (Fig. 1). Furthermore, given a graph \( \mathcal{H} \) with \( k \) vertices without monochromatic triangles, we can add to it a new vertex, join it to all vertices of \( \mathcal{H} \) except \( A \), and color each edge \( B X \) in the same way as \( A X \). The obtained graph obviously contains no monochromatic triangles. Applying this construction four times to the graph \( C_{5} \) we get an example like that of Fig. 2. ![](https://cdn.mathpix.com/cropped/2024_11_18_8e985d6b9c83aa3e9d0eg-568.jpg?height=338&width=396&top_left_y=1069&top_left_x=326)  Fig. 1 ![](https://cdn.mathpix.com/cropped/2024_11_18_8e985d6b9c83aa3e9d0eg-568.jpg?height=326&width=396&top_left_y=1079&top_left_x=868)  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 possible 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án. 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 \( c_{ij} \) be the color in which the edge \( (i, j) \) of \( H \) is colored, \( 1 \leq i < j \leq r(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 \( P_i \), \( i = 1, \ldots, r(k, l) - 1 \). If we color each edge of \( H \) between \( P_i \) and \( P_j \) (\( j < i \)) in the color \( c_{ij} \), 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 \).