Consider 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 such that whenever exactly edges are colored, the set of colored edges necessarily contains a triangle all of whose edges have the same color.
Solution
Consider a configuration where you have 9 points in space, with each pair of points joined by an edge, for a total of edges. We want to find the smallest such that if exactly edges are colored (either blue or red), there must exist a monochromatic triangle (a triangle with all edges of the same color).
The problem is equivalent to finding the smallest number such that every coloring of edges, using two colors, necessarily forms a monochromatic triangle. This is a classic application of Ramsey Theory, specifically the problem of finding for two colors, which states the minimum number of edges needed to ensure a monochromatic triangle in a complete graph.
From Ramsey Theory, we know:
meaning that in any two-coloring of a complete graph on 6 vertices, there exists a monochromatic triangle.
Therefore, if we have a complete graph , and we color edges without getting a monochromatic triangle, then must be greater than the maximum number of edges we can color without creating such a triangle.
A (complete graph on 5 vertices) does not necessarily have a monochromatic triangle if less than 10 edges are colored. Thus, we need to consider larger configurations. For , which has edges:
If we leave 3 edges uncolored, we are left with 33 colored edges. This will ensure that in (when 33 edges are colored), there must necessarily exist a monochromatic triangle.
Thus, the smallest number such that any coloring of edges guarantees a monochromatic triangle is: