MathDB

Consider a set of

n > 3

points in the plane, no three of which are collinear, and a natural number

k < n

. Prove the following statements:
(a) If

k \le \frac{n}{2}

, then each point can be connected with at least k other points by segments so that no three segments form a triangle.
(b) If

k \ge \frac{n}{2}

, and each point is connected with at least k other points by segments, then some three segments form a triangle.

Problem Statement