Moser spindle
Encyclopedia
In graph theory
, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser
and his brother William, with seven vertices and eleven edges. It is a unit distance graph
requiring four colors in any graph coloring
, and its existence can be used to prove that the chromatic number of the plane
is at least four.
As a unit distance graph, the Moser spindle is formed by two rhombi
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.
The Moser spindle may also be constructed graph-theoretically, without reference to a geometric embedding, using the Hajós construction
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
of the graph formed from the utility graph K3,3 by subdividing one of its edges.
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 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
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 is true), the chromatic number of the plane is the same as the largest chromatic number of any of its finite subgraphs; to date, no subgraph of the infinite unit distance graph has 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.
, 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
. The Moser spindle is also a Laman graph
, meaning that it forms a minimally rigid system 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
of the embedding and every bounded face is a pseudotriangle
with only three convex vertices.
The complement graph
of the Moser graph is a triangle-free graph
. 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.
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
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
of testing whether a given graph has a two-dimensional unit distance representation; the proof uses a reduction from 3SAT
in which the Moser spindle is used as the central truth-setting gadget
in the reduction.
The Moser spindle can also be used to prove a result in Euclidean Ramsey theory
: 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 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.
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, a branch of mathematics, the Moser spindle (also called the Mosers' spindle or Moser graph) is an undirected graph, named after mathematicians Leo Moser
Leo Moser
Leo Moser was an Austrian-Canadian mathematician, best known for his polygon notation....
and his brother William, with seven vertices and eleven edges. It is a unit distance graph
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...
requiring four colors in any graph coloring
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 of a graph such that no two adjacent vertices share the...
, and its existence can be used to prove that the chromatic number of the plane
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...
is at least four.
Construction
Rhombus
In Euclidean geometry, a rhombus or rhomb is a convex quadrilateral whose four sides all have the same length. The rhombus is often called a diamond, after the diamonds suit in playing cards, or a lozenge, though the latter sometimes refers specifically to a rhombus with a 45° angle.Every...
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.
The Moser spindle may also be constructed graph-theoretically, without reference to a geometric embedding, using the Hajós construction
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:...
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
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of the graph formed from the utility graph K3,3 by subdividing one of its edges.
Application to the Hadwiger–Nelson problem
The Hadwiger–Nelson problemHadwiger–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...
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 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 (graph theory)
In graph theory, a k-degenerate graph is an undirected graph in which every subgraph has a vertex of degree at most k: that is, some vertex in the subgraph touches k or fewer of the subgraph's edges. The degeneracy of a graph is the smallest value of k for which it is k-degenerate...
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
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
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
De Bruijn–Erdős theorem
In graph theory, the De Bruijn–Erdős theorem, proved by , states that, for every infinite graph and finite integer , can be colored by colors if and only if each of its finite subgraphs can be colored by colors...
(with the assumption that the axiom of choice is true), the chromatic number of the plane is the same as the largest chromatic number of any of its finite subgraphs; to date, no subgraph of the infinite unit distance graph has 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 graphPlanar 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...
, 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
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 Moser spindle is also a Laman graph
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 at most 2k −3 edges, and such that the whole graph...
, meaning that it forms a minimally rigid system 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
Convex hull
In mathematics, the convex hull or convex envelope for a set of points X in a real vector space V is the minimal convex set containing X....
of the embedding and every bounded face is a pseudotriangle
Pseudotriangle
In Euclidean plane geometry, a pseudotriangle is the simply connected subset of the plane that lies between any three mutually tangent convex sets...
with only three convex vertices.
The complement graph
Complement graph
In graph theory, the complement or inverse of a graph G is a graph H on the same vertices such that two vertices of H are adjacent if and only if they are not adjacent in G. That is, to generate the complement of a graph, one fills in all the missing edges required to form a complete graph, and...
of the Moser graph is a triangle-free graph
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 girth ≥ 4, graphs with no induced 3-cycle, or locally...
. 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.
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
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 maps adjacent vertices to adjacent vertices.-Definitions:...
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
NP-complete
In computational complexity theory, the complexity class NP-complete is a class of decision problems. A decision problem L is NP-complete if it is in the set of NP problems so that any given solution to the decision problem can be verified in polynomial time, and also in the set of NP-hard...
of testing whether a given graph has a two-dimensional unit distance representation; the proof uses a reduction from 3SAT
3sat
3sat is the name of a public, advertising-free, television network in Central Europe. The programming is in German and is broadcast primarily within Germany, Austria and Switzerland .3sat was established for cultural...
in which the Moser spindle is used as the central truth-setting gadget
Gadget (computer science)
In computer science and computational complexity theory, gadgets are often used to construct reductions from one problem to another. Each element of the first problem is converted to a gadget built from elements of the second problem...
in the reduction.
The Moser spindle can also be used to prove a result in Euclidean Ramsey theory
Ramsey theory
Ramsey theory, named after the British mathematician and philosopher Frank P. Ramsey, is a branch of mathematics that studies the conditions under which order must appear...
: 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 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
Independent set (graph theory)
In graph theory, an independent set or stable set is a set of vertices in a graph, no two of which are adjacent. That is, it is a set I of vertices such that for every two vertices in I, there is no edge connecting the two. Equivalently, each edge in the graph has at most one endpoint in I...
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.