MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Take a set of $2n$ points in the plane and assume that no open set of diameter $1$ contains more than $n$ of these points.

Question: can we pair up the points so that the distance between the points in a pair is at least $1$?

share|cite|improve this question
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 '12 at 3:00
Gjergji Zaimi, why false for $n=1$? – David Feldman Jun 16 '12 at 3:50
Oops, I meant "obviously true for $n=1$". – Gjergji Zaimi Jun 16 '12 at 4:14
up vote 4 down vote accepted

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.

share|cite|improve this answer
Thank you very much, it was most helpful! – TOM Jun 16 '12 at 10:35

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.