Unit distance graph

Paul Erdős (1946) posed the problem of estimating how many pairs of points in a set of ${\displaystyle n}$ points could be at unit distance from each other. In graph-theoretic terms, the question asks how dense a unit distance graph can be, and Erdős's publication on this question was one of the first works in extremal graph theory.[15] The hypercube graphs and Hamming graphs provide a lower bound on the number of unit distances, proportional to ${\displaystyle n\log n.}$ By considering points in a square grid with carefully chosen spacing, Erdős found an improved lower bound of the form

$${\displaystyle n^{1+c/\log \log n}}$$

for a constant ${\displaystyle c}$, and offered $500 for a proof of whether the number of unit distances can also be bounded above by a function of this form.[16] The best known upper bound for this problem is

$${\displaystyle {\sqrt[{3}]{\frac {29n^{4}}{4}}}\approx 1.936n^{4/3}.}$$

This bound can be viewed as counting incidences between points and unit circles, and is closely related to the crossing number inequality and to the Szemerédi–Trotter theorem on incidences between points and lines.[17]

For small values of ${\displaystyle n}$ (up to 14, as of 2022), the exact maximum number of possible edges is known. For ${\displaystyle n=2,3,4,\dots }$ these numbers of edges are:[18]

If a given graph ${\displaystyle G}$ is not a non-strict unit distance graph, neither is any supergraph ${\displaystyle H}$ of ${\displaystyle G}$. A similar idea works for strict unit distance graphs, but using the concept of an induced subgraph, a subgraph formed from all edges between the pairs of vertices in a given subset of vertices. If ${\displaystyle G}$ is not a strict unit distance graph, then neither is any other ${\displaystyle H}$ that has ${\displaystyle G}$ as an induced subgraph. Because of these relations between whether a subgraph or its supergraph is a unit distance graph, it is possible to describe unit distance graphs by their forbidden subgraphs. These are the minimal graphs that are not unit distance graphs of the given type. They can be used to determine whether a given graph ${\displaystyle G}$ is a unit distance graph, of either type. ${\displaystyle G}$ is a non-strict unit distance graph, if and only if ${\displaystyle G}$ is not a supergraph of a forbidden graph for the non-strict unit distance graphs. ${\displaystyle G}$ is a strict unit distance graph, if and only if ${\displaystyle G}$ is not an induced supergraph of a forbidden graph for the strict unit distance graphs.[8]

For both the non-strict and strict unit distance graphs, the forbidden graphs include both the complete graph ${\displaystyle K_{4}}$ and the complete bipartite graph ${\displaystyle K_{2,3}}$. For ${\displaystyle K_{2,3}}$, wherever the vertices on the two-vertex side of this graph are placed, there are at most two positions at unit distance from them to place the other three vertices, so it is impossible to place all three vertices at distinct points.[8] These are the only two forbidden graphs for the non-strict unit distance graphs on up to five vertices; there are six forbidden graphs on up to seven vertices[6] and 74 on graphs up to nine vertices. Because gluing two unit distance graphs (or subgraphs thereof) at a vertex produce strict (respectively non-strict) unit distance graphs, every forbidden graph is a biconnected graph, one that cannot be formed by this gluing process.[19]

The wheel graph ${\displaystyle W_{7}}$ can be realized as a strict unit distance graph with six of its vertices forming a unit regular hexagon and the seventh at the center of the hexagon. Removing one of the edges from the center vertex produces a subgraph that still has unit-length edges, but which is not a strict unit distance graph. The regular-hexagon placement of its vertices is the only one way (up to congruence) to place the vertices at distinct locations such that adjacent vertices are a unit distance apart, and this placement also puts the two endpoints of the missing edge at unit distance. Thus, it is a forbidden graph for the strict unit distance graphs,[20] but not one of the six forbidden graphs for the non-strict unit distance graphs. Other examples of graphs that are non-strict unit distance graphs but not strict unit distance graphs include the graph formed by removing an outer edge from ${\displaystyle W_{7}}$, and the six-vertex graph formed from a triangular prism by removing an edge from one of its triangles.[19]

For every algebraic number ${\displaystyle \alpha }$, it is possible to construct a unit distance graph ${\displaystyle G}$ in which some pair of vertices are at distance ${\displaystyle \alpha }$ in all unit distance representations of ${\displaystyle G}$.[21] This result implies a finite version of the Beckman–Quarles theorem: for any two points ${\displaystyle p}$ and ${\displaystyle q}$ at distance ${\displaystyle \alpha }$ from each other, there exists a finite rigid unit distance graph containing ${\displaystyle p}$ and ${\displaystyle q}$ such that any transformation of the plane that preserves the unit distances in this graph also preserves the distance between ${\displaystyle p}$ and ${\displaystyle q}$.[22] The full Beckman–Quarles theorem states that the only transformations of the Euclidean plane (or a higher-dimensional Euclidean space) that preserve unit distances are the isometries. Equivalently, for the infinite unit distance graph generated by all the points in the plane, all graph automorphisms preserve all of the distances in the plane, not just the unit distances.[23]

If ${\displaystyle \alpha }$ is an algebraic number of modulus 1 that is not a root of unity, then the integer combinations of powers of ${\displaystyle \alpha }$ form a finitely generated subgroup of the additive group of complex numbers whose unit distance graph has infinite degree. For instance, ${\displaystyle \alpha }$ can be chosen as one of the two complex roots of the polynomial ${\displaystyle z^{4}-z^{3}-z^{2}-z+1}$, producing an infinite-degree unit distance graph with four generators.[24]

The Hadwiger–Nelson problem concerns the chromatic number of unit distance graphs, and more specifically of the infinite unit distance graph formed from all points of the Euclidean plane. By the de Bruijn–Erdős theorem, which assumes the axiom of choice, this is equivalent to asking for the largest chromatic number of a finite unit distance graph. There exist unit distance graphs requiring five colors in any proper coloring,[25] and all unit distance graphs can be colored with at most seven colors.[26]

A seven-coloring of the infinite unit distance graph formed from all points of the plane, and the four-chromatic Moser spindle embedded as a unit distance graph

Answering another question of Paul Erdős, it is possible for triangle-free unit distance graphs to require four colors.[27]

The number of strict unit distance graphs on ${\displaystyle n\geq 4}$ labeled vertices is at most[2]

$${\displaystyle {\binom {n(n-1)}{2n}}=O\left(2^{{\bigl (}4+o(1){\bigr )}n\log _{2}n}\right),}$$

as expressed using big O notation and little o notation.