Maximum number of points at distance exactly one where distance between points is at least 1

This is the problem in question:

Let S = {$x_1,x_2,. . .,x_n$} be a set of points in the plane such that the distance between any two distinct points in S is at least one. Show that there are at most 3n pairs of points at distance exactly one.

Since this is a graph theory problem, I immediately want to find some way to represent it as a graph, but I don't know how to do that. My best guess is to represent the points as vertices, with two points adjacent only if they are at distance exactly one; that way the number of edges in the graph will be the number of pairs.

The problem is that I then need to know how to decide for any arbitrary number of such vertices what the rules are for whether or not they're allowed to be adjacent. I think that the most points a single point can be exactly 1 unit away from is 6 (forming a regular hexagon and its "center"), and each of those points would be exactly 1 away from 2 of the others, so it looks like I should get a result of 18 when n=7, for example. I suspect if I could obtain that rule, I might be able to go into the graph theory part of the problem and show how 3n is the most edges possible, but I don't know how to prove to begin with that that rule actually holds up, if it even does.

Solution 1:

Your idea of constructing the graph is good.

Hint: Proceed by induction. Consider a vertex (not on the edge) of the convex hull. Show that it can be connected to at most 3 other vertices.

Note: This is a common competition problem.