6
$\begingroup$

This is a problem I found in a graph theory text, but I can't figure it out.

Let $S$ be a set of $n$ points in a plane, the distance between any two of which is at least one. Show that there are at most $3n$ pairs of points of $S$ at distance exactly one.

Experimenting, I figured the way to get the most points of distance exactly 1 would be to lay out the points in a grid made out of equilateral triangles. While building up this grid, it seems that when adding a new vertex, I can connect it to 2 or 3 other points to have distance exactly 1, which implies that I can only add at most 3 new pairs of points 1 unit apart for every point I add, which suggests the result. Is there a nonhandwavey way to show this?

  • 0
    Or am I right thinking this is an over-shooting upper-bound. to keep the proof simple. (I think it would be fun to ask for a CLOSER bound!)2011-04-22

2 Answers 2

3

It's natural (especially since this is a graph theory text...) to turn the set $S$ into a graph by connecting two points (vertices) if they are exactly one unit apart. What can you say about this graph? Can you say something about the degrees of the vertices? What, in terms of this graph, are you trying to prove?

  • 0
    Yes, but you probably want to be a bit more formal and not use "the worst case scenario". You have $2e = \sum d_i$ where the sum is over all the vertices of which there are $n$. Now $d_i \leq 6$ for all $i$, so...2011-04-22
7

Each point can have at most $6$ neighbours at distance $1$, so it can be in at most $6$ pairs. Each pair contains $2$ points. So there can be at most $6n/2=3n$ such pairs.

  • 1
    You had me confused for a moment there :-) The distance between any two points is at least $1$, so you can't put any of the neighbours closer than in an equilateral triangle; since each of those takes up $60°$ of the circle, there can't be more than $6$ of them.2011-04-22