Unit distance graph

In mathematics, and 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 by an edge whenever the distance between the two points is exactly one. Edges of unit distance graphs sometimes cross each other, so they are not always planar; a unit distance graph without crossings is called a matchstick graph.

The Hadwiger–Nelson problem concerns the chromatic number of unit distance graphs. It is known that there exist unit distance graphs requiring four colors in any proper coloring, and that all such graphs can be colored with at most seven colors. Another important open problem concerning unit distance graphs asks how many edges they can have relative to their number of vertices.

The following graphs are unit distance graphs:

Any Cartesian product of unit distance graphs produces another unit distance graph. However, the same is not true for other commonly-used graph products (Horvat & Pisanski 2010).

Some sources define a graph as being a unit distance graph if its vertices can be mapped to distinct locations in the plane such that adjacent pairs are at unit distance apart, disregarding the possibility that some non-adjacent pairs might also be at unit distance apart. For instance, the Möbius-Kantor graph has a drawing of this type.

According to this looser definition of a unit distance graph, all generalized Petersen graphs are unit distance graphs (Žitnik, Horvat & Pisanski 2010). In order to distinguish the two definitions, the graphs in which non-edges are required to be a non-unit distance apart may be called strict unit distance graphs (Gervacio, Lim & Maehara 2008).

The graph formed by removing one of the spokes from the wheel graph W₇ is a subgraph of a unit distance graph, but is not a strict unit distance graph: there is 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 spoke at unit distance (Soifer 2008, p. 94).

...
Wikipedia