Moser spindle
The Moser spindle is a graph named after the brothers William Oscar Jules and Leo Moser . It is an undirected graph with seven nodes and eleven edges. The Moser spindle can be embedded in the plane as a unit distance graph and as a flat graph , but it is not a matchstick graph . One of its applications is to prove that the chromatic number of the plane is greater than or equal to four. This gives a lower bound for the Hadwiger-Nelson problem .
The Moser spindle is also known as the Hajós graph (after György Hajós ).
construction
The Moser spindle can be constructed with geometric means or, alternatively, with purely graph-theoretical considerations.
The starting point for the geometric construction is an equilateral triangle with an edge length of one, which is mirrored on one of its sides. The resulting figure is a diamond with interior angles of 60 ° and 120 °. Two such diamonds are now positioned in the plane in such a way that they share an acute-angled corner point and the two opposite corners have the same distance from each other. The eleven edges of the graph correspond to the sides of the equilateral triangles and the distance between the two acute-angled corners of the diamonds.
From a purely graph-theoretical point of view, the Moser spindle can be constructed using the Hajós construction , starting from two complete graphs K4 . With this construction, one edge is removed from both graphs. One pair of the respective end points of this distant edge is merged and the other pair is connected to a new edge.
Application to the Hadwiger – Nelson problem
The Hadwiger-Nelson problem investigates the minimum number of colors required to color a plane in such a way that every two points with a unit distance have different colors. We are looking for the chromatic number of that unit distance graph whose nodes are all points of the plane. The Moser spindle is a subgraph of that graph. It follows that at least as many colors are needed to color the plain as to color the Moser spindle.
It can be shown that the chromatic number of the Moser spindle is four: Since the Moser spindle contains triangles, at least three colors are necessary. If one assumes that three colors are sufficient, then the knot shared by the two diamonds and the two opposite corner points of the diamonds are the same color. This leads to a contradiction. However, four colors are sufficient to color the Moser spindle.
Four is thus a lower bound for the chromatic number of the plane.
The de Bruijn – Erdős theorem states that, assuming the axiom of choice, the chromatic number of an infinite graph is equal to the largest chromatic number of a finite subgraph. Until 2018, no finite subgraph was known that required more colors than the Moser spindle. The best known upper bound for the Hadwiger – Nelson problem is seven.
Other properties
The Moser spindle is a Laman graph , that is, it is a minimal rigid graph in the plane.
The graph complementary to the Moser spindle is a triangle-free graph . From this it follows that among three nodes of the Moser spindle (considered as a unit distance graph) there is always at least one pair of nodes that have a unit distance from each other.
When adding further edges, the unit distance property is always lost. In addition, there is no graph homomorphism that maps the Moser spindle to a smaller unit distance graph. These two properties were used by Horvat, Kratochvíl, and Pisanski to prove that testing whether a given graph has an embedding as a unit distance graph is an NP-hard problem.
An n-dimensional generalization of the Moser spindle plays an important role in proving the Beckman and Quarles theorem .
Individual evidence
- ^ W. and L. Moser: Solution to problem 10 . In: Can. Math. Bull. Volume 4 , 1961, pp. 187-189 .
- ^ A b c d A. Soifer: The Mathematical Coloring Book: Mathematics of Coloring and the Colorful Life of its Creators . Springer, New York 2008, ISBN 978-0-387-74640-1 , pp. 14-15 .
- ^ JA Bondy, USR Murty: Graph Theory . In: Graduate Texts in Mathematics . tape 244 . Springer, 2008, p. 358 , doi : 10.1007 / 978-1-84628-970-5 .
- ↑ a b G. Hajós: About a construction of graphs that cannot be n-colored . In: Wiss. Z. Martin Luther Univ. Halle-Wittenberg Math.-Nature. Row . tape 10 , 1961, pp. 116-117 .
- ↑ a b Boris Horvat, Jan Kratochvíl, Tomaž Pisanski: On the Computational Complexity of Degenerate Unit Distance Representations of Graphs . In: Lecture Notes in Computer Science . tape 6460 , 2011, p. 274-285 .
- ^ Peter Winkler: Puzzled: Distances Between Points on the Plane . In: Communications of the ACM . tape 54 , no. 11 , doi : 10.1145 / 2018396.2018422 .
- ^ W. Benz: Geometrical transformations with special consideration of the Lorentz transformation . BI-Wiss.-Verl., Mannheim (inter alia) 1992, ISBN 3-411-15071-8 , pp. 15-31 .