In mathematics

Mathematics

Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...

, and particularly geometric graph theory

Geometric graph theory

In mathematics, a geometric graph is a graph in which the vertices or edges are associated with geometric objects or configurations. Geometric graph theory is a specialization of graph theory that studies geometric graphs...

, 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

Planar graph

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints...

; a unit distance graph without crossings is called a matchstick graph

Matchstick graph

In geometric graph theory, a branch of mathematics, a matchstick graph is a graph that can be drawn in the plane in such a way that its edges are line segments with length one that do not cross each other. That is, it is a graph that has an embedding which is simultaneously a unit distance graph...

.

The Hadwiger–Nelson problem

Hadwiger–Nelson problem

In geometric graph theory, the Hadwiger–Nelson problem, named after Hugo Hadwiger and Edward Nelson, asks for the minimum number of colors required to color the plane such that no two points at distance one from each other have the same color. The answer is unknown, but has been narrowed down to...

 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.

Examples

The following graphs are unit distance graphs:

• Any cycle graph
  Cycle graph
  In graph theory, a cycle graph or circular graph is a graph that consists of a single cycle, or in other words, some number of vertices connected in a closed chain. The cycle graph with n vertices is called Cn...
  
  
• Any grid graph
• Any hypercube graph
• The Petersen graph
  Petersen graph
  In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named for Julius Petersen, who in 1898 constructed it...
  
  
• The Heawood graph
  Heawood graph
  In the mathematical field of graph theory, the Heawood graph is an undirected graph with 14 vertices and 21 edges, named after Percy John Heawood.-Combinatorial properties:...
  
   
• The wheel graph
  Wheel graph
  In the mathematical discipline of graph theory, a wheel graph Wn is a graph with n vertices, formed by connecting a single vertex to all vertices of an -cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle,...
  
   W₇
• The Moser spindle
  Moser spindle
  In graph theory, a branch of mathematics, the Moser spindle is an undirected graph, named after mathematicians Leo Moser and his brother William, with seven vertices and eleven edges...
  
  , the smallest 4-chromatic unit distance graph

Subgraphs of unit distance graphs

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 graph

Generalized Petersen graph

In graph theory, the generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph. The generalized...

s are unit distance graphs . 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 .

The graph formed by removing one of the spokes from the wheel graph

Wheel graph

In the mathematical discipline of graph theory, a wheel graph Wn is a graph with n vertices, formed by connecting a single vertex to all vertices of an -cycle. The numerical notation for wheels is used inconsistently in the literature: some authors instead use n to refer to the length of the cycle,...

 W₇ is a subgraph of a unit distance graph, but is not a strict unit distance graph: there is only one way (up to

Up to

In mathematics, the phrase "up to x" means "disregarding a possible difference in  x".For instance, when calculating an indefinite integral, one could say that the solution is f "up to addition by a constant," meaning it differs from f, if at all, only by some constant.It indicates that...

 congruence

Congruence (geometry)

In geometry, two figures are congruent if they have the same shape and size. This means that either object can be repositioned so as to coincide precisely with the other object...

) 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 .

Counting unit distances

posed the problem of estimating how many pairs of points in a set of n points could be at unit distance from each other. In graph theoretic terms, how dense can a unit distance graph be?

The hypercube graph provides a lower bound on the number of unit distances proportional to By considering points in a square grid with carefully chosen spacing, Erdős found an improved lower bound of the form


and offered a prize of $500 for determining whether or not the maximum number of unit distances can also be upper bounded by a function of this form . The best known upper bound for this problem, due to , is proportional to

this bound can also be viewed as counting incidences between points and unit circles, and is closely related to the Szemerédi–Trotter theorem

Szemerédi–Trotter theorem

The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n points and m lines in the plane,the number of incidences The Szemerédi–Trotter theorem is a mathematical result in the field of combinatorial geometry. It asserts that given n...

 on incidences between points and lines.

Representation of algebraic numbers and the Beckman–Quarles theorem

For any algebraic number

Algebraic number

In mathematics, an algebraic number is a number that is a root of a non-zero polynomial in one variable with rational coefficients. Numbers such as π that are not algebraic are said to be transcendental; almost all real numbers are transcendental...

 A, it is possible to find a unit distance graph G in which some pair of vertices are at distance A in all unit distance representations of G . This result implies a finite version of the Beckman–Quarles theorem

Beckman–Quarles theorem

In geometry, the Beckman–Quarles theorem, named after F. S. Beckman and D. A. Quarles, Jr., states that if a transformation of the Euclidean plane or a higher dimensional Euclidean space preserves unit distances, then it preserves all distances...

: for any two points p and q at distance A, there exists a finite rigid

Structural rigidity

In discrete geometry and mechanics, structural rigidity is a combinatorial theory for predicting the flexibility of ensembles formed by rigid bodies connected by flexible linkages or hinges.-Definitions:...

 unit distance graph containing p and q such that any transformation of the plane that preserves the unit distances in this graph preserves the distance between p and q . The full Beckman–Quarles theorem states that any transformation of the Euclidean plane (or a higher dimensional space) that preserves unit distances must be a congruence

Isometry

In mathematics, an isometry is a distance-preserving map between metric spaces. Geometric figures which can be related by an isometry are called congruent.Isometries are often used in constructions where one space is embedded in another space...

; that is, for the infinite unit distance graph whose vertices are all the points in the plane, any graph automorphism

Graph automorphism

In the mathematical field of graph theory, an automorphism of a graph is a form of symmetry in which the graph is mapped onto itself while preserving the edge–vertex connectivity....

 must be an isometry

Isometry

In mathematics, an isometry is a distance-preserving map between metric spaces. Geometric figures which can be related by an isometry are called congruent.Isometries are often used in constructions where one space is embedded in another space...

 .

Generalization to higher dimensions

The definition of a unit distance graph may naturally be generalized to any higher dimensional Euclidean space

Euclidean space

In mathematics, Euclidean space is the Euclidean plane and three-dimensional space of Euclidean geometry, as well as the generalizations of these notions to higher dimensions...

.
Any graph may be embedded as a set of points in a sufficiently high dimension; show that the dimension necessary to embed a graph in this way may be bounded by twice its maximum degree.

The dimension needed to embed a graph so that all edges have unit distance, and the dimension needed to embed a graph so that the edges are exactly the unit distance pairs, may greatly differ from each other: the 2n-vertex crown graph

Crown graph

In graph theory, a branch of mathematics, a crown graph on 2n vertices is an undirected graph with two sets of vertices ui and vi and with an edge from ui to vj whenever i ≠ j...

 may be embedded in four dimensions so that all its edges have unit length, but requires at least n − 2 dimensions to be embedded so that the edges are the only unit-distance pairs .

See also

• Unit disk graph
  Unit disk graph
  In geometric graph theory, a unit disk graph is the intersection graph of a family of unit circles in the Euclidean plane. That is, we form a vertex for each circle, and connect two vertices by an edge whenever the corresponding circles cross each other....
  
  , a graph on the plane that has an edge whenever two points are at distance at most one