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.

hogwartsxhoe5t

hogwartsxhoe5t

Answered question

2022-10-12

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 3 n pairs of points of S at distance exactly one.

Answer & Explanation

snowman8842

snowman8842

Beginner2022-10-13Added 12 answers

It's natural (especially since this is a graph theory text...) to turn the set 𝑆 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?
Chaim Ferguson

Chaim Ferguson

Beginner2022-10-14Added 4 answers

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 6 n / 2 = 3 n such pairs.

Do you have a similar question?

Recalculate according to your conditions!

Ask your question.
Get an expert answer.

Let our experts help you. Answer in as fast as 15 minutes.

Didn't find what you were looking for?