Graph Theory – Proving at Most 3n Pairs of Points with Distance 1 Given n Points in the Plane

euclidean-geometrygraph theoryplanar-graphs

Here's the problem:

Given n points in the plane, such that the euclidian distance between each pair
of points is at least 1. Show that there are at most 3n pairs of
points with distance exactly 1.

Well, this exercises is part of an assignment about planar graphs, so my intuition is to build such graph.

Then I defined the following graph:

let $G=(V,E)$ be a graph such that $\{e,v\}\in E \iff distance(u,v) =1 $.

Then, using contradiction to the assumption, I managed to prove that this graph is planar.

With that, knowing that planar graphs as at most $3n-6$ edges, I concluded that in particular they have at most $3n$ edges.

Does it make any sense?

Thanks

EDIT this is my proof for the planarity:

Assuming the graph is non-planar. Let a,b,c,d be vertices in the graph such that $ \{a,b\},\{c,d\} \in E$ and those edges intersect each other. Let $o$ be the intersection point. Assuming WLOG that $dist(b,o)<dist(a,o)$ and $dist(c,o)<dist(o,d)$ then both $dist(c,o),dist(b,o)<\frac{1}{2}$. Let's have a look at the triangle $\Delta boc$.
Let's use the following marks: $dist(o,b)=x$, $dist(o,c)=y$ and $dist(c,b)=z$
From the triangle inequality, we know that $|z|\leq |x|+|y|$, but $x,y<0.5$ Than $ z < 0.5+0.5=1$ In contradiction that each 2 points has distance of at least 1.

Best Answer

Your solution is perfectly correct.