In mathematics, particularly geometric graph theory, a unit distance graph is a graph formed from a collection of points in the Euclidean plane by connecting two points whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.
A problem posed by Paul Erdős known as the unit distance problem asks for the maximum possible number of unit-distance pairs determined by points in the Euclidean plane; equivalently, it asks for the maximum number of edges in a unit distance graph on vertices. The best known upper bound is The best known lower bound is (for sufficiently large . The number of colors required to color T unit distance graphs is also unknown; in the equivalent Hadwiger–Nelson problem for the plane, some unit distance graphs require five colors, and every unit distance graph can be colored with seven colors. For every algebraic number there is a unit distance graph with two vertices that must be at distance According to the Beckman–Quarles theorem, the only plane transformations that preserve all unit distance graphs are the isometries.
It is possible to construct a unit distance graph efficiently, given its points. Finding all unit distances has applications in pattern matching, where it can be a first step in finding congruent copies of larger patterns. However, determining whether a given graph can be represented as a unit distance graph is NP-hard, and more specifically complete for the existential theory of the reals.
Definition
The unit distance graph for a set of points in the plane is the undirected graph having those points as its vertices, with an edge between two vertices whenever their Euclidean distance is exactly one. An abstract graph is said to be a unit distance graph if it is possible to find distinct locations in the plane for its vertices, so that its edges have unit length and so that all non-adjacent pairs of vertices have non-unit distances. When this is possible, the abstract graph is isomorphic to the unit distance graph of the chosen locations. Alternatively, some sources use a broader definition, allowing non-adjacent pairs of vertices to be at unit distance. The resulting graphs are the subgraphs of the unit distance graphs (as defined here). Where the terminology may be ambiguous, the graphs in which non-edges must be a non-unit distance apart may be called strict unit distance graphs or faithful unit distance graphs. The subgraphs of unit distance graphs are equivalently the graphs that can be drawn in the plane using only one edge length. For brevity, this article refers to these as "non-strict unit distance graphs".
Unit distance graphs should not be confused with unit disk graphs, which connect pairs of points when their distance is less than or equal to one, and are frequently used to model wireless communication networks.
Examples The complete graph on two vertices is a unit distance graph, as is the complete graph on three vertices (the triangle graph), but not the complete graph on four vertices. Generalizing the triangle graph, every cycle graph is a unit distance graph, realized by a regular polygon. Two finite unit distance graphs, connected at a single shared vertex, yield another unit distance graph, as one can be rotated with respect to the other to avoid undesired additional unit distances. By thus connecting graphs, every finite tree or cactus graph may be realized as a unit distance graph.
Any Cartesian product of unit distance graphs produces another unit distance graph; however, the same is not true for some other common graph products. For instance, the strong product of graphs, applied to any two non-empty graphs, produces complete subgraphs with four vertices, which are not unit distance graphs. The Cartesian products of path graphs form grid graphs of any dimension, the Cartesian products of the complete graph on two vertices are the hypercube graphs, and the Cartesian products of triangle graphs are the Hamming graphs .
Other specific graphs that are unit distance graphs include the Petersen graph,; the Heawood graph, the wheel graph (the only wheel graph that is a unit distance graph), and the Moser spindle and Golomb graph (small 4-chromatic unit distance graphs). All generalized Petersen graphs, such as the Möbius–Kantor graph depicted, are non-strict unit distance graphs.
Matchstick graphs are a special case of unit distance graphs, in which no edges cross. Every matchstick graph is a planar graph, but some otherwise-planar unit distance graphs (such as the Moser spindle) have a crossing in every representation as a unit distance graph. Additionally, in the context of unit distance graphs, the term 'planar' should be used with care, as some authors use it to refer to the plane in which the unit distances are defined, rather than to a prohibition on crossings. The penny graphs are an even more special case of unit distance and matchstick graphs, in which every non-adjacent pair of vertices are more than one unit apart.
Properties Number of edges
posed the problem of estimating how many pairs of points in a set of 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.
Let this number be A construction with the hypercube graphs and Hamming graphs shows that By considering points in a square grid with carefully chosen spacing, Erdős found the improved lower bound for some constant The paper also established the upper bound
Because the upper bound is while the lower bound is dominated by any for any constant Erdős conjectured that, for any For a proof or a disproof of the conjecture he offered a prize of $300, then upped it to $500. In May 2026, this conjecture was disproven by an AI model by OpenAI, by a construction for which , where . The construction uses algebraic number theory, specifically the class field tower method. The bound was quickly improved to by Will Sawin. This is an instance of the various connections of distance graphs to algebraic numbers and rigidity. As a corollary, this disproves a conjecture of Erdős and Fishburn (Erdős offered $500 for a proof, but only $50 for a disproof).
In the other direction, the best known upper bound for this problem is 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.; ; ;
In 1959, Erdős and Leo Moser asked about the special case of this problem for the vertices of a convex polygon. In this case, the maximum number of unit distances is at most Only a linear lower bound, is known.
For small values of the exact maximum number of possible edges is known. For these numbers of edges are: The problem can be generalized to the Euclidean norms on For with even Erdős proved that For with odd Erdős and Pach proved that The case of is open. The best results are for the lower bound, and for the upper bound, for any
The problem can be generalized to arbitrary norms on arbitrary Given a norm define accordingly. The problem is solved in the generic case. Specifically, given any integer for almost all norms That is, the set of norms that violate this condition is meagre in the set of all norms of regarded as a metric space, metrized by the Hausdorff distance between the norm-unit balls. In this sense, the Euclidean norm over is special, since it is within this meagre set.
In the other direction, constructed a metric over that is similar to the Euclidean metric, but with which suggests that for the original question, improving upon the is going to use some subtle property of the Euclidean norm in particular.
Forbidden subgraphs If a given graph is not a non-strict unit distance graph, neither is any supergraph of . 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 is not a strict unit distance graph, then neither is any other that has 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 is a unit distance graph, of either type. is a non-strict unit distance graph, if and only if is not a supergraph of a forbidden graph for the non-strict unit distance graphs. is a strict unit distance graph, if and only if is not an induced supergraph of a forbidden graph for the strict unit distance graphs.
For both the non-strict and strict unit distance graphs, the forbidden graphs include both the complete graph and the complete bipartite graph . For , 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. 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 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.
The wheel graph 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, 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 , and the six-vertex graph formed from a triangular prism by removing an edge from one of its triangles.
Algebraic numbers and rigidity