MathDB

In the plane we are given a set

E

of 1991 points, and certain pairs of these points are joined with a path. We suppose that for every point of

E,

there exist at least 1593 other points of

E

to which it is joined by a path. Show that there exist six points of

E

every pair of which are joined by a path. Alternative version: Is it possible to find a set

E

of 1991 points in the plane and paths joining certain pairs of the points in

E

such that every point of

E

is joined with a path to at least 1592 other points of

E,

and in every subset of six points of

E

there exist at least two points that are not joined?

9