Unit-Distance Graph

A unit-distance graph is a graph having a straight-line drawing in the Euclidean plane in which distinct vertices occupy distinct points and every graph edge has length 1. Nonadjacent vertices may also be distance 1 apart. Because this definition constrains lengths rather than intersections, a unit-distance embedding need not be a topological embedding or a planar graph embedding. Since 1 is an integer, every unit-distance embedding is also an integral drawing. By definition, unit-distance graphs have graph dimension (with 0 and 1 corresponding to the trivial connected cases of the singleton graph and path graph , respectively).

The smallest dimension for which a graph has a unit-distance embedding in Euclidean space is called the graph dimension of .

For finite graphs, a disconnected graph is unit-distance iff each of its connected components is unit-distance. Similarly, a connected graph is unit-distance iff each of its blocks is unit-distance (Chilakamarri and Mahoney 1995; Globus and Parshall 2020). This is because biconnected components are joined in the original graph either at a single point at which they may be split or by graph bridges. Since bridges can always be drawn with unit length, if the components are all unit-distance, then so is the graph obtained by connecting them either directly or with bridges.

Determining if a graph is unit-distance is NP-hard (Schaefer 2013, pp. 461-482; Globus and Parshall 2020).

Any graph containing the complete bipartite graph (Erdős 1946, Chvátal 1972) or the complete graph (Chvátal 1972) as a subgraph is not a unit-distance graph (Horvat and Pisanski 2010). To see the former, draw unit circles around two points and note that the circles cannot intersect in three places. (However, the diamond graph (where is any edge) is unit-distance.) In addition, any graph with chromatic number greater than 7 is not a unit-distance graph (Horvat and Pisanski 2010).

The graph Cartesian product of two finite unit-distance graphs is also a unit-distance graph (Erdős et al. 1965, Buckley and Harary 1988, Horvat and Pisanski 2010). This immediately establishes the unit-distance status of a number of families of graphs.

Call a graph that is not unit-distance "forbidden," and call a forbidden graph minimal if each of its proper subgraphs is unit-distance. Purdy and Purdy (1988) attempted to classify the minimal forbidden graphs on 7 vertices, but their results contained errors. Chilakamarri and Mahoney (1995) subsequently proved that a graph on 7 or fewer vertices is unit-distance iff it contains none of the above six minimal graphs as a forbidden subgraph. (This result was also obtained independently by H. Parshall and E. Weisstein in April 2018, though Weisstein's set included graphs reducible to minimal ones by edge deletions.) Globus and Parshall (2020) found there to be 13 minimal forbidden 8-node graphs and 55 minimal forbidden 9-node graphs. This gives the numbers of minimal unit-distance forbidden graphs on , 2, ... nodes as 0, 0, 0, 1, 1, 1, 3, 13, 55, ... (OEIS A308349). The corresponding numbers of simple connected unit-distance graphs on , 2, ... nodes are 1, 1, 2, 5, 13, 51, 222, 1313, 9639, ... (OEIS A059103).

Unit-distance graphs are closely related to the Hadwiger-Nelson problem, which asks the chromatic number of the plane (i.e., the minimum number of colors needed to color the plane if no two points at unit distance one from one another are given the same color). The value is currently known to be 5, 6, or 7, but discovery of a unit-distance graph with chromatic number 6 or 7 would raise the known lower bound.

The following table gives the smallest known graphs of girth 4 and 5 with chromatic number 4 and a faithful unit-distance embedding, in which every pair of vertices at unit distance forms a graph edge. The girth-4 vertex count is a minimum under this embedding requirement (Soifer 2024, pp. 157-160). The girth-5 vertex count is an upper bound (Shukla 2026b, p. 1).

Dúcz and Varga (2026) constructed a 29-vertex unit-distance graph , called the snail graph, whose geometric fractional chromatic number is at least . Using two finite blow-up procedures, they proved the existence of a finite unit-distance graph in the plane with independence ratio . The order of was not given and was described as astronomically large. This answers a question of Erdős and implies that the fractional chromatic number of the plane is greater than 4. ChatGPT and Codex assisted the computational search and software development. Independent peer review had not been reported as of Sep. 21, 2026.

The 5-chromatic Shukla graphs constructed by Shukla (2026a) have 773, 5713, and 8168 vertices, with drawings inside open disks of radii , , and , respectively. The 773-vertex example is a vertex-critical graph. The author supplies certificates of non-4-colorability for all three graphs.

In contrast, Shukla (2026b) constructed the 43-vertex member of the Shukla graphs, with 83 edges, girth 5, and chromatic number 4. It lowers the previously known upper bound of 45, attained by the Hochberg-O'Donnell star graph, on the minimum number of vertices in such a graph. This graph is both 4-vertex-critical and 4-edge-critical. Its unit-distance embedding is the unique solution in a rational isolating box of 82 quadratic equations.

Tomon (2026) proved that every chromatic number attained by a finite graph with unit-length edges in , , can also be attained in the same dimension with arbitrarily large girth, even when every pair of points at distance 1 is required to be adjacent. In particular, for every integer , there is a unit-distance graph in the Euclidean plane with chromatic number 5 and girth at least . Tomon (2026) reports that a construction was found by ChatGPT Astra under the author's guidance.

A unit-distance graph that is rigid and contains a regular polygon as subgraph is known as a braced polygon.

Classes of graphs that are unit-distance include the following:

1. bishop, black bishop, and white bishop graphs,

2. book graphs ,

3. cactus graphs (Erdős et al. 1965),

4. camel graphs,

5. cube-connected cycle graphs for ,

6. cycle graphs ,

7. empty graphs (trivially),

8. gear graphs,

9. generalized Petersen graph (Žitnik et al. 2012),

10. giraffe graphs,

11. grid graphs (Horvat and Pisanski 2010),

12. Hamming graphs and ,

13. hypercube graphs (Erdős et al. 1965),

14. I graphs (Žitnik et al. 2012),

15. Jahangir graphs with and ,

16. ladder graphs ,

17. ladder rung graphs ,

18. Menger sponge graphs,

19. Mongolian tent graphs,

20. pan graphs,

21. path graphs ,

22. graphs formed by the vertices and edges of polyhexes,

23. graphs formed by the vertices and edges of polyiamonds,

24. graphs formed by the vertices and edges of polyominoes,

25. prism graphs (Horvat and Pisanski 2010),

26. Sierpiński carpet graphs,

27. Sierpiński gasket graphs,

28. stacked book graphs ,

29. stacked prism graphs (Horvat and Pisanski 2010),

30. star graphs ,

31. sunlet graphs ,

32. torus grid graphs ,

33. trees (Erdős et al. 1965),

34. triangular honeycomb acute knight graphs,

35. triangular honeycomb obtuse knight graphs,

36. web graphs, and

37. zebra graphs.

Möbius ladders are not unit-distance, as can be proven by hand or using the "rhombus logic" of Globus and Parshall (2020) and Alexeev et al. (2025) (B. Alexeev, pers. comm., Aug. 9, 2025). The king graphs contain as a subgraph for and so are also not unit-distance. Similarly, the -folded cube graphs contain as a subgraph for and so are not unit-distance.

The only unit-distance wheel graph is on 7 vertices (Buckley and Harary 1988).

Families of unit-distance connected circulant graphs include:

1. cycle graphs ,

2. graph Cartesian products of prism graphs and for odd , yielding torus grid graphs .

A number of unit-distance graphs are illustrated above.

The following table summarizes some named unit-distance graphs.

Many cubic symmetric graphs (excepting the tetrahedral graph, utility graph, and possibly others) have unit-distance embeddings, as illustrated above in embeddings mainly due to Gerbracht (2008, pers. comm., Dec. 2009-Jan. 2010).

Solving the Erdős unit distance problem amounts to finding a maximally dense unit-distance graph on a given number of vertices.