Suppose that the edges of a 10-point graph can be colored with two colors in such a way that the graph does not contain a monochromatic triangle. What is the maximum number of edges the graph can have?
The task is a modification of the 3rd problem of the 1992 International Mathematical Olympiad (see KöMaL 1993/1, pages 3-4).

We will also use the following theorem: if a graph has at least 6 points, then the graph or its complement definitely contains a triangle, or in other words: if the edges of a complete graph with at least 6 points are colored with two colors, then the graph definitely contains a monochromatic triangle.

A complete graph with 10 points has $\binom{10}{2}=45$ edges. We will show that if the graph has at least 41 edges (i.e., at most 4 edges are missing from the complete graph), then it always contains a monochromatic triangle. Additionally, we will provide an example of a graph with 40 edges that does not contain a monochromatic triangle.

From this, it follows that the graph can have at most 40 edges.

If at most 4 edges are missing from the complete graph, then select one endpoint of each missing edge, and leave out these at most 4 selected points from the graph. This way, we obtain a subgraph of the original graph that has at least 6 points and no "missing" edges, i.e., the subgraph is complete. According to the theorem mentioned earlier, the subgraph contains a monochromatic triangle. The triangle is also part of the original graph. This proves that if the graph has at least 41 edges, then it contains a monochromatic triangle.

Now we will provide an example of a 10-point, 40-edge graph whose edges can be colored such that it does not contain a monochromatic triangle (Figure 1). We note that among the 5 missing edges, no two can have a common endpoint, because otherwise, we could leave out four points (choosing one as the common endpoint of the two edges) such that the remaining 6-point graph is complete, which definitely contains a monochromatic triangle.

![](https://cdn.mathpix.com/cropped/2024_05_02_9a4d0b2d0fcad803c3d8g-1.jpg?height=537&width=578&top_left_y=954&top_left_x=321)

Figure 1

![](https://cdn.mathpix.com/cropped/2024_05_02_9a4d0b2d0fcad803c3d8g-1.jpg?height=536&width=588&top_left_y=1540&top_left_x=1208)

Figure 2

This condition already determines the graph we are looking for; we only need to specify the coloring.

For better clarity, we represent the red edges with solid lines and do not draw the blue edges. The 5 missing edges from the complete graph are indicated by dashed lines. From Figure 2, it is clear that the graph does not contain a monochromatic triangle.

Remarks. 1. The auxiliary theorem can be proven as follows. Let $A$ be any point in the graph. Since at least 5 edges originate from $A$, among these edges, there are three of the same color, say red. Let the endpoints of these be $B, C$, and $D$.

If two of the points $B, C, D$ are connected by a red edge, then these two points together with $A$ form a red triangle. If none of the edges of the triangle $BCD$ are red, then $BCD$ is a blue triangle.

![](https://cdn.mathpix.com/cropped/2024_05_02_9a4d0b2d0fcad803c3d8g-2.jpg?height=466&width=487&top_left_y=130&top_left_x=800)

Figure 3

2. The problem can be generalized to graphs with any number of points using Turán's theorem.

Turán's theorem answers the question of how many edges a graph with $n$ points can have at most if it does not contain a complete subgraph with $k$ points; it even describes the maximum edge graphs.

A maximum edge graph is obtained by dividing the $n$ points into "roughly" $k-1$ equal parts (i.e., the difference in the number of points in any two parts is at most 1) and connecting those points that fall into different parts.

In the problem—based on the auxiliary theorem—only graphs that do not contain a complete subgraph with 6 points are relevant. What is the maximum number of edges such a graph can have?

Knowing Turán's theorem, divide the points into 5 roughly equal parts and connect those pairs of points that fall into different parts (in the olympiad problem, one 1-element and four 2-element parts were used, while in our problem, five 2-element parts were used).

The interesting thing is that this graph can be colored with two colors such that it does not contain a monochromatic triangle (Figure 3, Figure 4).
![](https://cdn.mathpix.com/cropped/2024_05_02_9a4d0b2d0fcad803c3d8g-2.jpg?height=472&width=1066&top_left_y=1222&top_left_x=518)

Figure 4

The uniqueness of the graph also follows from Turán's theorem.

Géza Kós