Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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? –  a little don Apr 22 '11 at 6:13
    
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!) –  a little don Apr 22 '11 at 6:14

2 Answers 2

up vote 3 down vote accepted

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?

share|improve this answer
    
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. –  Hobbie Apr 22 '11 at 5:56
    
Remember that the points must all have a distance of at least 1 from each other, not just from the one at the center. –  Alon Amit Apr 22 '11 at 6:00
    
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? –  Hobbie Apr 22 '11 at 6:05
    
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? –  Alon Amit Apr 22 '11 at 6:10
    
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. –  Hobbie Apr 22 '11 at 6:17

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.

share|improve this answer
    
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? –  Hobbie Apr 22 '11 at 5:54
    
Sorry, you're right of course. Let me rethink that... –  joriki Apr 22 '11 at 5:58
    
I believe you are right, due to the fact that all points must be at least one away from each other. My mistake. –  Hobbie Apr 22 '11 at 6:16
    
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. –  joriki Apr 22 '11 at 6:17

Your Answer

 
discard

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.