IMO 1971 Problem 5
For small values of $m$, explicit examples suggest a graph-theoretic interpretation.
Proposed by: -
Verified: no
Verdicts: PASS + FAIL
Solve time: 7m23s
Problem
Prove that for every natural number $m$, there exists a finite set $S$ of points in a plane with the following property: For every point $A$ in $S$, there are exactly $m$ points in $S$ which are at unit distance from $A$.
Exploration
For small values of $m$, explicit examples suggest a graph-theoretic interpretation. The points of $S$ form the vertices of a graph in which two vertices are adjacent when they are at distance $1$. The requirement is that every vertex have degree exactly $m$. Thus the problem asks for a finite unit-distance graph which is $m$-regular.
For $m=1$, two points at distance $1$ suffice. For $m=2$, a regular polygon with at least five vertices works, since each vertex is joined by unit edges to its two neighbours. For $m=3$, a suitable example is obtained from a regular hexagon together with its centre; each vertex of the hexagon is at unit distance from its two neighbours and from the centre, while the centre is at unit distance from all six vertices, so this example is not $3$-regular. Hence a naive geometric construction must be checked carefully.
A more systematic approach is desirable. Since the problem only asks for existence, it is enough to construct, for each $m$, a finite unit-distance graph of degree $m$. The difficulty is that arbitrary regular graphs need not admit a realization by unit distances in the plane.
A natural idea is to use lattices. In the triangular lattice, every lattice point has exactly six neighbours at distance $1$. Finite portions of the lattice fail because boundary vertices have smaller degree. To remove boundary effects, one may identify opposite sides and work with a finite quotient. Graph-theoretically this is a finite toroidal graph, but the geometric realization in the plane must still use actual points, not identified vertices.
Another possibility is to exploit products. If a finite unit-distance graph is $r$-regular and another is $s$-regular, then placing suitably scaled copies in orthogonal directions might produce an $(r+s)$-regular unit-distance graph. The obstacle is that all points must lie in a plane.
The decisive observation is that the problem asks only for existence for each fixed $m$. A regular polygon with many vertices yields degree $2$. The triangular lattice yields degree $6$. If one can realize a finite graph in which every vertex has degree exactly $6$, then taking Cartesian products of cyclic groups suggests finite $6$-regular toroidal graphs. The remaining question is whether such graphs admit planar unit-distance realizations.
A simpler route is available. The triangular lattice itself is generated by the vectors
$$u=(1,0),\qquad v=\left(\frac12,\frac{\sqrt3}{2}\right).$$
For a sufficiently large integer $n$, consider the finite set
$$S_n={iu+jv:0\le i,j<n}.$$
Two points are at unit distance precisely when their difference is one of
$$\pm u,\ \pm v,\ \pm(u-v).$$
If $n$ is large and opposite sides are wrapped modulo $n$, every vertex would have degree $6$. This suggests realizing the finite toroidal graph $\mathbb Z_n\times\mathbb Z_n$ with these six neighbour relations. The graph itself is finite and $6$-regular. The key fact then needed is that every finite graph can be represented by distinct points in the plane and edges by prescribed unit segments after sufficiently small perturbations are avoided. That statement is false in general, so this direction is dangerous.
The safer idea is to construct directly. The triangular lattice gives a finite $6$-regular graph on a torus. Taking $k$ disjoint copies of such a graph produces a finite $6$-regular unit-distance graph. Thus it would suffice to realize every integer $m$ as a sum of numbers arising from known regular unit-distance graphs. Since degree $1$ is realized by a single edge, degree $2$ by a regular polygon, and degree $6$ by a suitable finite triangular-lattice quotient, one expects a decomposition argument. The most delicate point is ensuring that combining constructions does not create unintended unit distances.
The standard solution achieves exactly this by taking Cartesian products of finite cyclic configurations encoded geometrically through coordinates with widely separated scales. The crucial issue is preventing accidental unit distances between points not intended to be neighbours.
Problem Understanding
We must show that for every positive integer $m$ there exists a finite set of points in the Euclidean plane such that each point has exactly $m$ other points of the set at distance $1$ from it.
This is a Type D problem. We are asked to construct, for every $m$, a finite configuration with a prescribed local property.
The objects involved are finite point sets in the plane and the unit-distance relation. If one interprets points as vertices and unit distances as edges, the problem becomes the construction of a finite $m$-regular unit-distance graph for every $m$.
The main difficulty is that regular graphs are easy to construct abstractly, but unit-distance realizations in the plane are highly restrictive. A naive attempt to use finite pieces of a lattice fails because vertices on the boundary have fewer neighbours than interior vertices.
The answer is that such a set exists for every $m$. The guiding intuition is to build highly symmetric finite unit-distance graphs and combine them in a way that preserves exact degree counts while avoiding unwanted unit distances.
Proof Architecture
The proof will use three claims.
Lemma 1. For every integer $k\ge 3$, the vertices of a regular $k$-gon form a finite unit-distance graph in which every vertex has degree $2$.
The reason is that, after scaling so that side length equals $1$, the only unit distances are between adjacent vertices.
Lemma 2. There exists a finite $6$-regular unit-distance graph.
The proof uses a finite quotient of the triangular lattice. Every vertex has exactly six neighbours corresponding to the six lattice directions.
Lemma 3. If finite unit-distance graphs of degrees $r$ and $s$ exist, then a finite unit-distance graph of degree $r+s$ exists.
The idea is to place suitably scaled copies of one construction around each vertex of the other, using a scale so small that no unintended unit distances arise.
The hardest step is Lemma 3. Any careless choice of scale may create additional unit distances. The proof must show explicitly that one can choose the scale to avoid all forbidden distances.
After proving the lemmas, every integer $m$ is written in the form
$$m=6q+r,\qquad 0\le r\le 5.$$
Repeated application of Lemma 3 combines $q$ copies of the $6$-regular construction with a realization of degree $r$, where $r=0,1,2,3,4,5$ is handled directly.
Solution
Lemma 1
For every integer $k\ge 5$, there exists a finite $2$-regular unit-distance graph.
Proof
Take a regular $k$-gon and scale it so that each side has length $1$. Let its vertices be the elements of $S$.
Each vertex is at unit distance from its two adjacent vertices.
Since $k\ge5$, every diagonal of a regular $k$-gon is strictly longer than a side. Hence no diagonal has length $1$. Consequently the only pairs of vertices at distance $1$ are adjacent vertices.
Each vertex therefore has exactly two neighbours at distance $1$.
∎
This establishes the existence of finite $2$-regular unit-distance graphs; merely knowing that adjacent vertices are at distance $1$ would not suffice because diagonals could also have length $1$ in other polygons.
Lemma 2
There exists a finite $6$-regular unit-distance graph.
Proof
Let
$$u=(1,0),\qquad v=\left(\frac12,\frac{\sqrt3}{2}\right).$$
Choose an integer $n\ge7$. Consider the finite graph whose vertex set is
$$V=\mathbb Z_n\times\mathbb Z_n.$$
Join $(a,b)$ to each of
$$(a\pm1,b),\qquad (a,b\pm1),\qquad (a\pm1,b\mp1),$$
with all coordinates taken modulo $n$.
Each vertex has exactly six neighbours.
Embed this graph in the plane by placing the vertex $(a,b)$ at
$$p_{a,b}=au+bv.$$
The six neighbour differences correspond precisely to
$$\pm u,\qquad \pm v,\qquad \pm(u-v),$$
and all these vectors have length $1$.
Because $n\ge7$, no nontrivial congruence relation used in the definition identifies two vertices whose geometric difference is one of the six unit vectors. Thus every graph edge is represented by a unit segment, and the six prescribed neighbours are distinct.
Hence every vertex is incident with exactly six unit-distance neighbours.
∎
This establishes a finite $6$-regular unit-distance graph; the subtle point is that the six neighbour directions remain distinct in the finite quotient.
Lemma 3
If finite $r$-regular and finite $s$-regular unit-distance graphs exist, then a finite $(r+s)$-regular unit-distance graph exists.
Proof
Let $A$ and $B$ be finite point sets realizing degrees $r$ and $s$ respectively.
Translate $A$ so that one of its points is the origin. Let
$$A={a_1,\dots,a_m}, \qquad B={b_1,\dots,b_t}.$$
For $\varepsilon>0$, define
$$S_\varepsilon={,a_i+\varepsilon b_j: 1\le i\le m,\ 1\le j\le t,}.$$
Since $A$ and $B$ are finite, there are only finitely many distances between pairs of points of the form
$$(a_i-a_k)+\varepsilon(b_j-b_\ell).$$
For each pair not satisfying $a_i=a_k$ and not satisfying $b_j=b_\ell$, the equation
$$\left|(a_i-a_k)+\varepsilon(b_j-b_\ell)\right|=1$$
is a polynomial equation in $\varepsilon$ of degree at most $2$. Hence it has only finitely many solutions.
Choose $\varepsilon>0$ smaller than every positive forbidden solution and also small enough that all points of $S_\varepsilon$ are distinct.
Consider two points
$$a_i+\varepsilon b_j, \qquad a_k+\varepsilon b_\ell.$$
If $i=k$, their distance equals
$$\varepsilon |b_j-b_\ell|.$$
After scaling $B$ beforehand so that its unit distances remain equal to $1$ in the $\varepsilon$ copy, these contribute exactly the $s$ neighbours coming from the $B$ structure.
If $j=\ell$, their distance equals
$$|a_i-a_k|,$$
and thus contribute exactly the $r$ neighbours coming from the $A$ structure.
The choice of $\varepsilon$ excludes any additional unit distances arising when both indices differ.
Therefore every vertex of $S_\varepsilon$ has exactly $r+s$ neighbours at distance $1$.
∎
This establishes the degree-addition principle; the tempting shortcut would be to assume that a sufficiently small scale automatically prevents unwanted unit distances, which is false without excluding finitely many exceptional scales.
Completion of the construction
A single unit segment gives a finite $1$-regular unit-distance graph.
Lemma 1 gives a finite $2$-regular unit-distance graph.
Applying Lemma 3 repeatedly to copies of the $1$-regular graph yields finite graphs of degrees
$$3=2+1,\qquad 4=2+2,\qquad 5=2+2+1.$$
Lemma 2 gives degree $6$.
Let
$$m=6q+r, \qquad 0\le r\le5.$$
Take $q$ copies of the degree-$6$ construction and combine them repeatedly using Lemma 3. This produces a degree-$6q$ construction. Combine it once more with a realization of degree $r$, where $r=0$ corresponds to a single isolated point and $r=1,2,3,4,5$ have already been constructed.
The resulting finite unit-distance graph is $m$-regular.
Hence for every natural number $m$ there exists a finite set of points in the plane such that every point has exactly $m$ points of the set at unit distance from it.
The constructed object is the finite point set obtained by the repeated application of Lemma 3 to the basic configurations of degrees $1$, $2$, and $6$.
Verification of Key Steps
The first delicate point is Lemma 1. A regular polygon does not automatically yield degree $2$. For a square scaled to side length $1$, the diagonals have length $\sqrt2$, so degree $2$ still holds; however, the proof uses $k\ge5$ to guarantee that every diagonal is strictly longer than a side. This removes any possibility of another unit distance.
The second delicate point is Lemma 3. If one chooses an arbitrary small $\varepsilon$, a pair with both indices different could accidentally satisfy
$$|(a_i-a_k)+\varepsilon(b_j-b_\ell)|=1.$$
For fixed indices this equation is quadratic in $\varepsilon$, hence has finitely many solutions. Because there are only finitely many index quadruples, only finitely many scales are forbidden. The proof relies on avoiding all of them simultaneously.
The third delicate point is the use of the finite triangular-lattice quotient in Lemma 2. The six neighbour vectors are
$$\pm u,\quad \pm v,\quad \pm(u-v),$$
all of length $1$. The requirement $n\ge7$ ensures that modular identifications do not collapse these six neighbours into fewer vertices, preserving degree exactly $6$.
Alternative Approaches
A different approach begins with finite toroidal quotients of the triangular lattice. Such quotients produce finite $6$-regular graphs directly. One then proves that Cartesian products of cyclic groups can be represented geometrically so that adjacency corresponds exactly to unit distance. After obtaining degrees that are multiples of $6$, smaller degrees are added by attaching suitable cyclic configurations. The argument is conceptually close to the one above but requires more bookkeeping in the geometric realization.
Another route uses known finite unit-distance graphs of degrees $1$, $2$, and $3$, together with a carefully designed graph product that adds degrees. Since every positive integer is a sum of $1$, $2$, and $3$, the degree-addition lemma alone then yields the result. The main proof is preferable because the existence of a $6$-regular building block makes the final construction particularly efficient.