graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

, named after mathematicians

Leo Moser Leo Moser (11 April 1921, Vienna – 9 February 1970, Edmonton) was an Austrian-Canadian mathematician, best known for his polygon notation. A native of Vienna, Leo Moser immigrated with his parents to Canada at the age of three. He received his ...

and his brother William, with seven vertices and eleven edges. It is a

unit distance graph 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 graph ...

requiring four colors in any

graph coloring In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

, and its existence can be used to prove that the chromatic number of the plane is at least four.. The Moser spindle has also been called the Hajós graph after

György Hajós György Hajós (February 21, 1912, Budapest – March 17, 1972, Budapest) was a Hungarian mathematician who worked in group theory, graph theory, and geometry.. Biography Hajós was born February 21, 1912, in Budapest; his great-grandfathe ...

, as it can be viewed as an instance of the

Hajós construction In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold. The construction Let ...

. However, the name "Hajós graph" has also been applied to a different graph, in the form of a triangle inscribed within a hexagon.

Construction

As a unit distance graph, the Moser spindle is formed by two

rhombi In plane Euclidean geometry, a rhombus (plural rhombi or rhombuses) is a quadrilateral whose four sides all have the same length. Another name is equilateral quadrilateral, since equilateral means that all of its sides are equal in length. The ...

with 60 and 120 degree angles, so that the sides and short diagonals of the rhombi form equilateral triangles. The two rhombi are placed in the plane, sharing one of their acute-angled vertices, in such a way that the remaining two acute-angled vertices are a unit distance apart from each other. The eleven edges of the graph are the eight rhombus sides, the two short diagonals of the rhombi, and the edge between the unit-distance pair of acute-angled vertices. Hajos construction

The Moser spindle may also be constructed graph-theoretically, without reference to a geometric embedding, using the

starting with two complete graphs on four vertices. This construction removes an edge from each complete graph, merges two of the endpoints of the removed edges into a single vertex shared by both cliques, and adds a new edge connecting the remaining two endpoints of the removed edge. Another way of constructing the Moser spindle is as the

complement graph In the mathematical field of graph theory, the complement or inverse of a graph is a graph on the same vertices such that two distinct vertices of are adjacent if and only if they are not adjacent in . That is, to generate the complement of a ...

of the graph formed from the

utility graph As a topic of economics, utility is used to model worth or value. Its usage has evolved significantly over time. The term was introduced initially as a measure of pleasure or happiness as part of the theory of utilitarianism by moral philosopher ...

''K''_3,3 by subdividing one of its edges.

Application to the Hadwiger–Nelson problem

The

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 1 from each other have the same color. ...

asks how many colors are needed to color the points of the Euclidean plane in such a way that each pair of points at unit distance from each other are assigned different colors. That is, it asks for the

chromatic number In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...

of the infinite graph whose vertices are all the points in the plane and whose edges are all pairs of points at unit distance. The Moser spindle requires four colors in any graph coloring: in any three-coloring of one of the two rhombi from which it is formed, the two acute-angled vertices of the rhombi would necessarily have the same color as each other. But if the shared vertex of the two rhombi has the same color as the two opposite acute-angled vertices, then these two vertices have the same color as each other, violating the requirement that the edge connecting them have differently-colored endpoints. This contradiction shows that three colors are impossible, so at least four colors are necessary. Four colors are also sufficient to color the Moser spindle, a fact that follows for instance from the fact that its

degeneracy Degeneracy, degenerate, or degeneration may refer to: Arts and entertainment * ''Degenerate'' (album), a 2010 album by the British band Trigger the Bloodshed * Degenerate art, a term adopted in the 1920s by the Nazi Party in Germany to descri ...

is three. An alternative proof that the Moser spindle requires four colors follows from the Hajós construction. Both of the complete graphs from which the Moser spindle is formed require four colors, and the Hajós construction preserves this property.. Even more directly, each independent set in the Moser spindle has at most two vertices, so it takes at least four independent sets to cover all seven vertices. Since the Moser spindle is a subgraph of the infinite unit distance graph of the plane, the graph of the plane also requires at least four colors in any coloring. By the de Bruijn–Erdős theorem (with the assumption that the

axiom of choice In mathematics, the axiom of choice, or AC, is an axiom of set theory equivalent to the statement that ''a Cartesian product of a collection of non-empty sets is non-empty''. Informally put, the axiom of choice says that given any collectio ...

is true), the chromatic number of the plane is the same as the largest chromatic number of any of its finite subgraphs; until the discovery of a family of 5-chromatic unit distance graphs in 2018, no subgraph of the infinite unit distance graph had been found that requires a larger number of colors than the Moser spindle. However, the best upper bound for the chromatic number of the plane is seven, significantly higher than the number of colors required for the Moser spindle.

Other properties and applications

The Moser spindle is a

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. In other words, it can be drawn in such a way that no edges cross ...

, meaning that it can be drawn without crossings in the plane. However, it is not possible to form such a drawing with straight line edges that is also a unit distance drawing; that is, it is not a

matchstick graph In geometric graph theory, a branch of mathematics, a matchstick graph is a Graph (discrete mathematics), graph that can be Graph drawing, drawn in the plane in such a way that its edges are line segments with length one that do not cross each ...

. The Moser spindle is also a

Laman graph In graph theory, the Laman graphs are a family of sparse graphs describing the minimally rigid systems of rods and joints in the plane. Formally, a Laman graph is a graph on ''n'' vertices such that, for all ''k'', every ''k''-vertex subgraph has ...

, meaning that it forms a minimally

rigid system In discrete geometry and mechanics, structural rigidity is a combinatorics, combinatorial theory for predicting the flexibility of ensembles formed by rigid body, rigid bodies connected by flexible Linkage (mechanical), linkages or hinges. Defin ...

when embedded in the plane. As a planar Laman graph, it is the graph of a pointed pseudotriangulation, meaning that it can be embedded in the plane in such a way that the unbounded face is the

convex hull In geometry, the convex hull or convex envelope or convex closure of a shape is the smallest convex set that contains it. The convex hull may be defined either as the intersection of all convex sets containing a given subset of a Euclidean space ...

of the embedding and every bounded face is a

pseudotriangle In Euclidean plane geometry, a pseudotriangle (''pseudo-triangle'') is the simply connected subset of the plane that lies between any three mutually tangent convex sets. A pseudotriangulation (''pseudo-triangulations'') is a partition of a region ...

with only three convex vertices.. The

of the Moser graph is a

triangle-free graph In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with ...

. Thus, the unit distance embedding of the Moser graph may be used to solve the problem of placing seven points in the plane in such a way that every triple of points contains at least one pair at unit distance from each other.. Solution, issue 12, December 2011, . Adding any edge to the Moser spindle results in a graph that cannot be embedded in the plane as a unit distance graph, and there does not exist a

graph homomorphism In the mathematical field of graph theory, a graph homomorphism is a mapping between two graphs that respects their structure. More concretely, it is a function between the vertex sets of two graphs that maps adjacent vertices to adjacent verti ...

from the Moser spindle to any smaller unit distance graph. These two properties of the Moser spindle were used by to show the

NP-hardness In computational complexity theory, NP-hardness ( non-deterministic polynomial-time hardness) is the defining property of a class of problems that are informally "at least as hard as the hardest problems in NP". A simple example of an NP-hard pr ...

of testing whether a given graph has a two-dimensional unit distance representation; the proof uses a reduction from

3SAT In logic and computer science, the Boolean satisfiability problem (sometimes called propositional satisfiability problem and abbreviated SATISFIABILITY, SAT or B-SAT) is the problem of determining if there exists an interpretation that satisfie ...

in which the Moser spindle is used as the central truth-setting

gadget A gadget is a mechanical device or any ingenious article. Gadgets are sometimes referred to as '' gizmos''. History The etymology of the word is disputed. The word first appears as reference to an 18th-century tool in glassmaking that was develo ...

in the reduction.. The Moser spindle can also be used to prove a result in Euclidean

Ramsey theory Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that focuses on the appearance of order in a substructure given a structure of a known size. Problems in Ramsey theory typically ask a ...

: if ''T'' is any triangle in the plane, and the points of the plane are two-colored black and white, then there is either a black translate of ''T'' or a pair of white points at unit distance from each other. For, let ''M'' be a unit-distance embedding of the Moser spindle, and let ''M'' + ''T'' be the

Minkowski sum In geometry, the Minkowski sum (also known as dilation) of two sets of position vectors ''A'' and ''B'' in Euclidean space is formed by adding each vector in ''A'' to each vector in ''B'', i.e., the set : A + B = \. Analogously, the Minkowski ...

of ''M'' and ''T''. If ''M'' + ''T'' has no white unit-distance pair, then each of the three copies of the Moser spindle in ''M'' + ''T'' must have at most two white points, because the white points in each copy must form an independent set and the largest independent set in the Moser spindle has size two. Therefore, among the seven vertices of the Moser spindle, there are at most six that have a white copy in ''M'' + ''T'', so there must be one of the seven vertices all of whose copies are black. But then the three copies of this vertex form a translate of ''T''.. See also , Problem 40.26, p. 496.

References

External links

*{{mathworld, title=Moser Spindle, urlname=MoserSpindle Individual graphs Planar graphs