Moser spindle

The Moser spindle is a graph, which was named after the brothers William and Leo Moser. It involves an undirected graph with seven nodes and eleven edges. The Moser spindle can be embedded as a unit - distance graph and a planar graph in the plane, but is no match graph. One of its applications is the proof that the chromatic number of the plane is greater than or equal to four. This yields a lower bound for the Hadwiger -Nelson problem.

The Moser spindle is also known as the Hajos graph known ( by Gyorgy Hajos ).

Construction

The Moser spindle can be geometric forms or, alternatively, construct with purely graph-theoretical considerations.

The starting point for the geometrical construction is an equilateral triangle of side length one, which is mirrored on one side thereof. The resulting figure is a rhombus with interior angles 60 ° and 120 °. Two such diamonds are now positioned in the plane that they share an acute-angled corner and the two respective opposite corners from each other have the unit distance. 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.

Pure graph-theoretical can the Moser spindle by means of the Hajos construction, starting from two complete graph K4 construct. In this design, one edge is removed from both graphs. Of the respective end points of the distal edge, a pair of folded and the other pair is connected to a new edge.

Application to the Hadwiger -Nelson problem

Hadwiger the Nelson problem examines the minimum required number of colors, for coloring a plane such that any two points spaced unit have different colors. So Wanted is 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 for the coloring of the plane at least as many colors as needed to color the Moser spindle.

It can be shown that the number of chromatic Moser spindle four is: Since the spindle Moser triangles includes at least three colors are required. Assuming that suffice three colors, then have the node, which is shared by both diamonds and the two respective opposite corners of the diamonds of the same color. This leads to a contradiction. Four colors are sufficient, however, to color the Moser spindle.

Four is thus a lower bound for the chromatic number of the plane.

The set of de Bruijn - Erdős states that assuming the axiom of choice, the chromatic number of infinite graphs is equal to the maximum chromatic number of a finite subgraph. So far, no finite subgraph is known who needs 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, ie it is a minimal strarrer graph in the plane.

The complementary to the Moser spindle graph is a triangle-free graph. It follows that under the three nodes of the Moser spindle (seen as a unit distance graph ) is always at least one pair of nodes is, the distance from each unit has.

When adding further edges always losing the unit distance property. In addition, there is no Graphenhomomorphismus, which reflects the Moser spindle to a smaller unit distance graph. These two properties were used by Horvat, Kratochvil and Pisanski to prove that testing whether a given graph has an embedding as a unit - distance graph is a NP- hard problem.

An n -dimensional generalization of the Moser spindle plays an important role in the proof of the theorem of Beckman and Quarles.