Moser spindle
| Moser spindle | |
|---|---|
 |
|
| Named after | Leo Moser, William Moser |
| Vertices | 7 |
| Edges | 11 |
| Radius | 2 |
| Diameter | 2 |
| Girth | 3 |
| Automorphisms | 8 |
| Chromatic number | 4 |
| Chromatic index | 4 |
| Properties |
planar unit distance Laman graph |
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.
The Moser spindle has also been called the Hajós graph after György Hajós, as it can be viewed as an instance of the Hajós construction. However, the name "Hajós graph" has also been applied to a different graph, in the form of a triangle inscribed within a hexagon.
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.
The Hadwiger–Nelson problem 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.
...
Wikipedia