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
    I think there should be a lower upper bound than 3n. We're looking at an equilateral triangular lattice. Given n vertices... how many edges? for 3, 4, 5, and 6 I can't get anywhere near 3n... might it be the case that it becomes possible to approach 3n only when n is large?2011-04-22
  • 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
    This is actually precisely the hint on the weblog accompanying the book, but I didn't see the connection? I thought the max degree would be $n-1$, by arranging $n-1$ vertices around one other, at a distance of 1.2011-04-22
  • 0
    Remember that the points must all have a distance of at least 1 from *each other*, not just from the one at the center.2011-04-22
  • 0
    So the most we can put is $6$ around the circumference, then each vertex has degree at most $6$? So around every point we can have at most 6 pairs, but each is counted twice, once for each end vertex, so dividing gives $3n$ pairs, at most?2011-04-22
  • 0
    Once you've shown that the max degree is 6, you can drop the language of "around every point" etc. - there's no more geometry, just graph theory. You have a graph with n vertices and maximum degree 6; how many edges can it have, at most?2011-04-22
  • 0
    Okay, since the degree sum is twice the size of the edge set, we have that 6n=2e, or 3n=e, in the worst case scenario.2011-04-22
  • 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
6

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.

  • 0
    Why is this the case? I thought of this, since six equilateral triangles make up a hexagon, but what if we simply arranged all points except one point in a circle or radius 1 around that one vertex? Then that vertex would have $n-1$ neighbors, right?2011-04-22
  • 0
    Sorry, you're right of course. Let me rethink that...2011-04-22
  • 0
    I believe you are right, due to the fact that all points must be at least one away from each other. My mistake.2011-04-22
  • 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