13
$\begingroup$

This question from earlier today asks (paraphrasing here):

Is there a configuration of $7$ points in the Euclidean plane such that, given any $3$ of the $7$ points, at least $2$ of them are $1$ unit apart?

One such configuration, given in this answer, is the set of blue points in this diagram; the red line segments all have unit length:

enter image description here

This is an embedding of the Moser Spindle graph.

This raises a natural question:

Is this the unique such configuration up to Euclidean motions?

$\endgroup$
11
+100
$\begingroup$

The answer is yes; the given configuration is the unique such configuration up to Euclidean transformations. I advise to keep pencil and paper at hand when checking the proof.

EDIT: I have completed the proof, and revised most of the earlier part to make the entire proof more 'streamlined'.

Let $P_1,\ldots,P_7$ seven points in the Euclidean plane, such that out of every three points there are at least two at unit distance. Two points are called neighbours if they are at unit distance.

Proposition 1. Every pair of points $P_i$ and $P_j$ has at most two common neighbours.

Proof. Common neighbours of $P_i$ and $P_j$ are on the unit circles centered at $P_i$ and $P_j$. Two circles intersect in at most two points in the Euclidean plane.

Lemma 2. Every point $P_i$ has at least three neighbours.

Proof. Suppose toward a contradiction that $P_i$ has fewer than three neighbours. Then there exist four distinct points $Q_1$, $Q_2$, $Q_3$ and $Q_4$ among the seven points, all distinct from $P_i$, such that $P_i$ and $Q_j$ are not neighbours for $j\in\{1,2,3,4\}$. Because two of the three points $P_i$, $Q_j$ and $Q_k$ must be neighbours for any pair of distinct $j,k\in\{1,2,3,4\}$ we see that the $Q_j$ are all neighbours. Hence they are the vertices of a rhombus whose diagonals are of the same length as its side, which is of course a contradiction.

Lemma 3. Every point $P_i$ has at most four neighbours.

Proof. Suppose toward a contradiction that $P_i$ has at least five neighbours. Then there exist five distinct neighbours $Q_1$, $Q_2$, $Q_3$, $Q_4$ and $Q_5$ of $P_i$, which are then on the unit circle centered at $P_i$. The $Q_j$ cannot all be neighbours by the same argument as in the previous lemma, so without loss of generality $Q_1$ and $Q_2$ are not neighbours. Out of each triplet of points $$(Q_1,Q_2,Q_3)\qquad(Q_1,Q_2,Q_4)\qquad(Q_1,Q_2,Q_5),$$ a pair must be neighbours. Because $Q_1$ and $Q_2$ have at most two common neighbours with $P_i$, without loss of generality $Q_3$ and $Q_4$ neighbour $Q_1$, and $Q_5$ neighbours $Q_2$. Note that $Q_3$ and $Q_4$ cannot be neighbours as otherwise all pairs out of $Q_1$, $Q_2$, $Q_3$ and $Q_4$ would be neighbours, which we saw before is impossible. Considering the triplet $(Q_2,Q_3,Q_4)$ we see that, again without loss of generality, the points $Q_2$ and $Q_3$ are neighbours. But then $Q_3$ and $Q_5$ are a distance of $\sqrt{3}$ apart, as are $Q_4$ and $Q_5$. A picture says a thousand words:

enter image description here

Hence among the points $Q_3$, $Q_4$ and $Q_5$ there is no pair of neighbours, a contradiction.

Corollary 4. The number of points with four neighbours is odd.

Proof. Conider the graph with the seven points as its vertices and the pairs of neighbours as its edges. The total degree of the graph, i.e. the sum of the degrees of its vertices, is even. As every vertex has either degree three or four by the lemmas above, the number of vertices of degree three is even and hence the number of vertices of degree four is odd.

Proposition 5. Points with four neighbours are neighbours.

Proof. Two points $P_i$ and $P_j$ have at most two common neighbours by proposition 1. If they have precisely two common neighbours then they each have two more neighbours, all four of which are distinct. If these neighbours are also distinct from $P_i$ and $P_j$ this yields a total of eight points, a contradiction.

Lemma 5. There is precisely one point with four neighbours, and all other points have three neighbours.

Proof. By the corollary there cannot be fewer points with four neighbours. Suppose toward a contradiction that there are more. Then by the corollary there are at least three, say $P_i$, $P_j$ and $P_k$, and by the proposition they are all neighbours. Then each of these three points has two more neighbours, and if these were all distinct we would have a total of nine points. Hence two pairs of neighbours must coincide, so without loss of generality $P_i$ has common neighbours $Q_j$ and $Q_k$ with $P_j$ and $P_k$, distinct from $P_k$ and $P_j$. A picture illustrates the situation:

enter image description here

By assumption $P_j$ has a fourth neighbour $R_j$. Because $P_k$ and $Q_j$ are not neighbours $R_j$ must neighbour of one of them. If $R_j$ neighbours $P_k$ then $Q_j$, $Q_k$ and $R_j$ are all at distance $2$ from eachother, a contradiction. See also the picture:

enter image description here

Hence $R_j$ neighbours $Q_j$, and entirely analogously $P_k$ has a fourth neighbour $R_k$ which then neighbours $Q_k$. Again a picture make things clear:

enter image description here

But now no two of $P_i$, $R_j$ and $R_k$ are neighbours, a contradiction.

Theorem 6. Up to Euclidean transformations there is a unique configuration of seven points in the Euclidean plane with the property that for any three of the points, two of them are at unit distance.

Proof. By lemma 5 such a configuration has a unique point $P_1$ with four neighbours $P_2$, $P_3$, $P_4$ and $P_5$. There must be a pair of neighbours among $P_2$, $P_3$ and $P_4$, so without loss of generality $P_2$ and $P_3$ are neighbours. The remaining points $P_6$ and $P_7$ each have three neighbours and don't neighbour $P_1$. As they can each have at most two common neighbours with $P_1$ they must neighbour eachother. Then they each have precisely two common neighbours with $P_1$, and without loss of generality (i.e. after swapping $P_2$ and $P_3$, and $P_6$ and $P_7$ if necessary) $P_2$ and $P_6$ are neighbours and $P_5$ and $P_7$ are neighbours. So far we have the following configuration:

enter image description here

Now the third neighbour of $P_7$ must be either $P_3$ or $P_4$. If $P_7$ neighbours $P_3$ then $P_4$ must neighbour both $P_5$ and $P_6$, and now every point other than $P_1$ has precisely three neighbours. This yields the following graph:

enter image description here

Note that no two of $P_2$, $P_4$ and $P_7$ are neighbours by lemma 5, a contradiction. It follows that $P_7$ neighbours $P_4$.

Suppose toward a contradiction that $P_4$ and $P_5$ are not neighbours. Without loss of generality (i.e. after swapping $P_4$ and $P_5$ if necessary) $P_4$ neighbours $P_6$ and $P_5$ neighbours $P_3$, and again every point other than $P_1$ has precisely three neighbours. This yields the following graph:

enter image description here

Note that no two of $P_2$, $P_4$ and $P_5$ are neighbours by lemma 5, a contradiction. It follows that $P_4$ and $P_5$ are neighbours. Then also $P_3$ and $P_6$ are neighbours, corresponding to the configuration given in the question:

enter image description here

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.