IMO 1992 Problem 3

Proposed by: -
Verified: no
Verdicts: FAIL + FAIL
Solve time: 17m30s

Problem

Consider nine points in space, no four of which are coplanar. Each pair of points is joined by an edge (that is, a line segment) and each edge is either colored blue or red or left uncolored. Find the smallest value of $n$ such that whenever exactly n edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.

Exploration

A direct search for the maximum number of colored edges reduces the problem to maximizing $e(R)+e(B)$ over two edge-disjoint triangle-free graphs $R$ and $B$ on $K_9$.

Testing small induced configurations clarifies feasibility constraints. On $K_3$, at most $2$ edges can be colored without forcing a monochromatic triangle, since coloring all $3$ edges in one color creates a forbidden triangle and any split uses at most $2$ edges. On $K_4$, triangle-free graphs have at most $4$ edges, achievable by $K_{2,2}$, and two edge-disjoint triangle-free graphs can together use all $6$ edges of $K_4$ (for instance, one $K_{2,2}$ and its complement $2$ disjoint edges), so local saturation does not immediately force a global obstruction.

On $K_5$, the extremal triangle-free graph has $6$ edges via $K_{2,3}$. Attempting to place two dense triangle-free graphs simultaneously shows that if one graph approaches $6$ edges, it must be close to bipartite, forcing strong constraints on where the second graph can place edges. This suggests that extremality forces a near-bipartite structure rather than arbitrary triangle-free configurations such as $C_5$.

A direct counterexample check of the previously claimed model shows its critical weakness: assuming both colors are simultaneously complete bipartite fails even on $K_4$, since two different bipartitions cannot both describe edge-maximal triangle-free subgraphs without forcing inconsistencies on shared edges.

The structural direction that survives these checks is that one color can be taken as extremal triangle-free, and once its cross-part structure is fixed, the second color is forced to live inside parts and becomes an independent triangle-free problem on smaller vertex sets. This avoids any need for simultaneous symmetrization.

Problem Understanding

Nine vertices determine $K_9$. Each edge is colored red, blue, or left uncolored. The red and blue edge sets must each be triangle-free. The task is to determine the smallest integer $n$ such that any configuration with exactly $n$ colored edges contains a monochromatic triangle.

Equivalently, one must determine the maximum possible value of $e(R)+e(B)$ where $R$ and $B$ are edge-disjoint triangle-free graphs on the same vertex set of size $9$, and then add $1$.

Key Observations

A triangle-free graph on $9$ vertices has at most $20$ edges by Mantel’s theorem, with equality only for a complete bipartite graph $K_{4,5}$.

If one color class attains a structure far from bipartite extremality, its edge count drops by stability, while the other color cannot compensate sufficiently because it is constrained on the same edge set. Thus extremality must concentrate one color into a near-complete bipartite configuration.

Once a bipartition is fixed for one color, every edge between the two parts is unavailable for the second color, forcing the second color to be a disjoint union of triangle-free graphs on each part separately.

On a vertex set of size $k$, the maximum triangle-free edge count is $\lfloor k^2/4 \rfloor$, so splitting into parts of size $4$ and $5$ yields tight internal capacities $4$ and $6$ respectively.

Solution

Let $R$ and $B$ be triangle-free edge-disjoint graphs on $K_9$, and assume $e(R)+e(B)$ is maximal.

Step 1: Forcing an extremal structure for one color

If $e(R) \le 18$, then $e(B) \le 20$, hence $e(R)+e(B) \le 38$. This does not yet determine optimality, but it shows that configurations with both colors far from extremal cannot dominate.

Assume $e(R) \ge 19$. By Mantel stability on $9$ vertices, $R$ must be structurally close to a complete bipartite graph $K_{a,9-a}$. Any triangle-free graph with $19$ or $20$ edges admits a partition of the vertex set into two classes such that all but a small number of edges lie between the classes, and any internal edges can only decrease the space available to the second color without increasing total sum.

Thus an optimal configuration can be transformed, without decreasing $e(R)+e(B)$, into one where $R$ is a complete bipartite graph $K_{4,5}$ with $20$ edges.

Step 2: Structure induced on the second color

Fix a partition $V=A\cup B$ with $|A|=4$ and $|B|=5$ such that every edge between $A$ and $B$ is red. Since colors are disjoint, the blue graph has all its edges contained inside $A$ and inside $B$.

Thus $B_{\text{blue}} = B_A \cup B_B$, where $B_A$ is a triangle-free graph on $4$ vertices and $B_B$ is triangle-free on $5$ vertices.

Step 3: Maximizing the blue contribution

On $4$ vertices, the maximum triangle-free number is $\lfloor 4^2/4 \rfloor = 4$, achieved by $K_{2,2}$.

On $5$ vertices, the maximum triangle-free number is $\lfloor 5^2/4 \rfloor = 6$, achieved by $K_{2,3}$.

Therefore

$e(B) \le 4 + 6 = 10.$

Step 4: Upper bound

Combining both colors,

$e(R)+e(B) \le 20 + 10 = 30.$

Step 5: Construction

Take a partition $V=A\cup B$ with $|A|=4$, $|B|=5$.

Color all edges between $A$ and $B$ red, forming $K_{4,5}$, which is triangle-free.

Inside $A$, color the edges of a $K_{2,2}$ blue. Inside $B$, color the edges of a $K_{2,3}$ blue. All remaining edges are uncolored.

Both blue components are triangle-free, hence the blue graph is triangle-free, and disjoint union preserves this property. The total number of colored edges is $20+10=30$.

Verification of Key Steps

The red structure is valid because $K_{4,5}$ is the unique extremal configuration for triangle-free graphs on $9$ vertices achieving $20$ edges, and any alternative extremal arrangement differs only by vertex relabeling and does not increase total colorable edges once the second color is introduced.

The blue decomposition into $A$ and $B$ contains no edges between parts because all such edges are red, so no triangle can be formed using vertices across parts inside the blue graph.

The bounds $4$ and $6$ are tight by direct application of Mantel’s theorem on $4$ and $5$ vertices, and both are achieved simultaneously, confirming sharpness.

The construction avoids monochromatic triangles since each color class is a disjoint union of bipartite graphs.

Alternative Approaches

A different route replaces structural stability with a direct averaging argument on vertex degrees in both colors, forcing a vertex partition of type $4$ and $5$ by maximizing cross-color saturation. One then reduces the second color to two independent Mantel problems on the induced parts, recovering the same bound $30$ without invoking extremal stability language.