## On distances between points on the plane

Take a set of 2n points on the plane and assume that no open set of diameter 1 contains more than n of these points. Question: con we pair up the points so that the distance between the points in a pair is at least 1?

-
Obviously false for $n=1$. For $n=2$ a counterexample is an equilateral triangle of side $1+\epsilon$ and it's center... – Gjergji Zaimi Jun 16 at 3:00
Gjergji Zaimi, why false for $n=1$? – David Feldman Jun 16 at 3:50
Oops, I meant "obviously true for $n=1$". – Gjergji Zaimi Jun 16 at 4:14

In Gjergi's $n=2$ counterexample, the center is an isolated point of the graph you'd like to match. One way to save your question might simply rule that out.

But consider your question without the hypothesis: When can we pair up $2n$ points so that the distance between the points in a pair is at least 1? General matching theory says yes, one can, whenever there is no Tutte obstruction. That means whenever you can't remove $k$ points and leave a graph with more than $k$ odd components. Now for two points to lie in distinct components is a strong condition: no path with big steps can connect them. In particular the distance between the points cannot be more than 1, and they can't both lie more than 1 unit away from any common third point.

Now one can get many components of size 1 by having many points clustered close together, which is roughly what your hypothesis meant to rule out. But even arranging points along a line, one can get many components and not all of them consisting of isolated points.

Hope that helps...sorry, don't have time to work this out further now.

-
 Thank you very much, it was most helpful! – TOM Jun 16 at 10:35