MathDB
Minimum number of segments

Source:

September 5, 2010
pigeonhole principlegraph theorycombinatorics unsolvedcombinatorics

Problem Statement

Let nn points be given arbitrarily in the plane, no three of them collinear. Let us draw segments between pairs of these points. What is the minimum number of segments that can be colored red in such a way that among any four points, three of them are connected by segments that form a red triangle?