| 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 |
| Table of graphs and parameters | |
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,[1] 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.[2]
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.[3] However, the name "Hajós graph" has also been applied to a different graph, in the form of a triangle inscribed within a hexagon.[4]
- ^ Moser, L.; Moser, W. (1961), "Solution to problem 10", Can. Math. Bull., 4: 187–189, doi:10.1017/S0008439500025753, S2CID 246244722.
- ^ Soifer, Alexander (2008), The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators, New York: Springer, pp. 14–15, ISBN 978-0-387-74640-1.
- ^ Bondy, J. A.; Murty, U. S. R. (2008), Graph Theory, Graduate Texts in Mathematics, vol. 244, Springer, p. 358, doi:10.1007/978-1-84628-970-5, ISBN 978-1-84628-969-9.
- ^ Berge, C. (1989), "Minimax relations for the partial q-colorings of a graph", Discrete Mathematics, 74 (1–2): 3–14, doi:10.1016/0012-365X(89)90193-3, MR 0989117.