Moser spindle

Last updated
Moser spindle
Moser spindle pseudotriangulation.svg
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]

Contents

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]

Construction

The Moser spindle embedded as a unit distance graph in the plane, together with a seven-coloring of the plane. Hadwiger-Nelson.svg
The Moser spindle embedded as a unit distance graph in the plane, together with a seven-coloring of the plane.

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.

Hajos construction of the Moser spindle Hajos construction.svg
Hajós construction of the Moser spindle

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. [5]

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. [6]

Application to the Hadwiger–Nelson problem

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. [2]

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. [5] Even more directly, each independent set in the Moser spindle has at most two vertices, [7] 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; until the discovery of a family of 5-chromatic unit distance graphs in 2018, no subgraph of the infinite unit distance graph had 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. [2]

Other properties and applications

The Moser spindle is a planar graph, 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. [8] 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. [9]

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. [2] [10]

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 Horvat, Kratochvíl & Pisanski (2011) 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. [8]

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. [7]

See also

Related Research Articles

<span class="mw-page-title-main">Petersen graph</span> Cubic graph with 10 vertices and 15 edges

In the mathematical field of graph theory, the Petersen graph is an undirected graph with 10 vertices and 15 edges. It is a small graph that serves as a useful example and counterexample for many problems in graph theory. The Petersen graph is named after Julius Petersen, who in 1898 constructed it to be the smallest bridgeless cubic graph with no three-edge-coloring.

This is a glossary of graph theory. Graph theory is the study of graphs, systems of nodes or vertices connected in pairs by lines or edges.

<span class="mw-page-title-main">Outerplanar graph</span> Non-crossing graph with vertices on outer face

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Turán graph</span> Balanced complete multipartite graph

The Turán graph, denoted by , is a complete multipartite graph; it is formed by partitioning a set of vertices into subsets, with sizes as equal as possible, and then connecting two vertices by an edge if and only if they belong to different subsets. Where and are the quotient and remainder of dividing by , the graph is of the form , and the number of edges is

In graph theory, a uniquely colorable graph is a k-chromatic graph that has only one possible (proper) k-coloring up to permutation of the colors. Equivalently, there is only one way to partition its vertices into k independent sets and there is no way to partition them into k − 1 independent sets.

<span class="mw-page-title-main">Critical graph</span>

In graph theory, a critical graph is an undirected graph all of whose subgraphs have smaller chromatic number. In such a graph, every vertex or edge is a critical element, in the sense that its deletion would decrease the number of colors needed in a graph coloring of the given graph. The decrease in the number of colors cannot be by more than one.

<span class="mw-page-title-main">Edge coloring</span> Problem of coloring a graphs edges such that meeting edges do not match

In graph theory, a proper edge coloring of a graph is an assignment of "colors" to the edges of the graph so that no two incident edges have the same color. For example, the figure to the right shows an edge coloring of a graph by the colors red, blue, and green. Edge colorings are one of several different types of graph coloring. The edge-coloring problem asks whether it is possible to color the edges of a given graph using at most k different colors, for a given value of k, or with the fewest possible colors. The minimum required number of colors for the edges of a given graph is called the chromatic index of the graph. For example, the edges of the graph in the illustration can be colored by three colors but cannot be colored by two colors, so the graph shown has chromatic index three.

<span class="mw-page-title-main">Wheel graph</span> Cycle graph plus universal vertex

In the mathematical discipline of graph theory, a wheel graph is a graph formed by connecting a single universal vertex to all vertices of a cycle. A wheel graph with n vertices can also be defined as the 1-skeleton of an (n – 1)-gonal pyramid. Some authors write Wn to denote a wheel graph with n vertices ; other authors instead use Wn to denote a wheel graph with n + 1 vertices, which is formed by connecting a single vertex to all vertices of a cycle of length n. The rest of this article uses the former notation.

<span class="mw-page-title-main">Hadwiger conjecture (graph theory)</span>

In graph theory, the Hadwiger conjecture states that if is loopless and has no minor then its chromatic number satisfies . It is known to be true for . The conjecture is a generalization of the four-color theorem and is considered to be one of the most important and challenging open problems in the field.

<span class="mw-page-title-main">Dual graph</span> Graph representing faces of another graph

In the mathematical discipline of graph theory, the dual graph of a planar graph G is a graph that has a vertex for each face of G. The dual graph has an edge for each pair of faces in G that are separated from each other by an edge, and a self-loop when the same face appears on both sides of an edge. Thus, each edge e of G has a corresponding dual edge, whose endpoints are the dual vertices corresponding to the faces on either side of e. The definition of the dual depends on the choice of embedding of the graph G, so it is a property of plane graphs rather than planar graphs. For planar graphs generally, there may be multiple dual graphs, depending on the choice of planar embedding of the graph.

<span class="mw-page-title-main">Hadwiger–Nelson problem</span> Mathematical 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 1 from each other have the same color. The answer is unknown, but has been narrowed down to one of the numbers 5, 6 or 7. The correct value may depend on the choice of axioms for set theory.

<span class="mw-page-title-main">Geometric graph theory</span> Subfield of graph theory

Geometric graph theory in the broader sense is a large and amorphous subfield of graph theory, concerned with graphs defined by geometric means. In a stricter sense, geometric graph theory studies combinatorial and geometric properties of geometric graphs, meaning graphs drawn in the Euclidean plane with possibly intersecting straight-line edges, and topological graphs, where the edges are allowed to be arbitrary continuous curves connecting the vertices; thus, it can be described as "the theory of geometric and topological graphs". Geometric graphs are also known as spatial networks.

<span class="mw-page-title-main">Unit distance graph</span> Geometric graph with unit edge lengths

In mathematics, 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 whenever the distance between them is exactly one. To distinguish these graphs from a broader definition that allows some non-adjacent pairs of vertices to be at distance one, they may also be called strict unit distance graphs or faithful unit distance graphs. As a hereditary family of graphs, they can be characterized by forbidden induced subgraphs. The unit distance graphs include the cactus graphs, the matchstick graphs and penny graphs, and the hypercube graphs. The generalized Petersen graphs are non-strict unit distance graphs.

<span class="mw-page-title-main">Grötzsch graph</span> Triangle-free graph requiring four colors

In the mathematical field of graph theory, the Grötzsch graph is a triangle-free graph with 11 vertices, 20 edges, chromatic number 4, and crossing number 5. It is named after German mathematician Herbert Grötzsch, who used it as an example in connection with his 1959 theorem that planar triangle-free graphs are 3-colorable.

<span class="mw-page-title-main">Halin graph</span> Mathematical tree with cycle through leaves

In graph theory, a Halin graph is a type of planar graph, constructed by connecting the leaves of a tree into a cycle. The tree must have at least four vertices, none of which has exactly two neighbors; it should be drawn in the plane so none of its edges cross, and the cycle connects the leaves in their clockwise ordering in this embedding. Thus, the cycle forms the outer face of the Halin graph, with the tree inside it.

In graph theory, the De Bruijn–Erdős theorem relates graph coloring of an infinite graph to the same problem on its finite subgraphs. It states that, when all finite subgraphs can be colored with colors, the same is true for the whole graph. The theorem was proved by Nicolaas Govert de Bruijn and Paul Erdős (1951), after whom it is named.

<span class="mw-page-title-main">Apollonian network</span> Graph formed by subdivision of triangles

In combinatorial mathematics, an Apollonian network is an undirected graph formed by a process of recursively subdividing a triangle into three smaller triangles. Apollonian networks may equivalently be defined as the planar 3-trees, the maximal planar chordal graphs, the uniquely 4-colorable planar graphs, and the graphs of stacked polytopes. They are named after Apollonius of Perga, who studied a related circle-packing construction.

In graph theory, a branch of mathematics, the Hajós construction is an operation on graphs named after György Hajós (1961) that may be used to construct any critical graph or any graph whose chromatic number is at least some given threshold.

<span class="mw-page-title-main">Golomb graph</span> Undirected unit-distance graph requiring four colors

In graph theory, the Golomb graph is a polyhedral graph with 10 vertices and 18 edges. It is named after Solomon W. Golomb, who constructed it as a unit distance graph that requires four colors in any graph coloring. Thus, like the simpler Moser spindle, it provides a lower bound for the Hadwiger–Nelson problem: coloring the points of the Euclidean plane so that each unit line segment has differently-colored endpoints requires at least four colors.

The Earth–Moon problem is an unsolved problem on graph coloring in mathematics. It is an extension of the planar map coloring problem, and was posed by Gerhard Ringel in 1959. In mathematical terms, it seeks the chromatic number of biplanar graphs. It is known that this number is at least 9 and at most 12.

References

  1. ↑ Moser, L.; Moser, W. (1961), "Solution to problem 10", Can. Math. Bull., 4: 187–189, doi: 10.1017/S0008439500025753 , S2CID   246244722 .
  2. 1 2 3 4 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 .
  3. ↑ 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 .
  4. ↑ 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 .
  5. 1 2 Hajós, G. (1961), "Über eine Konstruktion nicht n-färbbarer Graphen", Wiss. Z. Martin-Luther-Univ. Halle-Wittenberg Math.-Natur. Reihe, 10: 116–117.
  6. ↑ Gervacio, Severino V.; Lim, Yvette F.; Maehara, Hiroshi (2008), "Planar unit-distance graphs having planar unit-distance complement", Discrete Mathematics, 308 (10): 1973–1984, doi: 10.1016/j.disc.2007.04.050 , MR   2394465 .
  7. 1 2 Burkert, Jeffrey; Johnson, Peter (2011), "Szlam's lemma: mutant offspring of a Euclidean Ramsey problem from 1973, with numerous applications", Ramsey theory, Progr. Math., vol. 285, Birkhäuser/Springer, New York, pp. 97–113, doi:10.1007/978-0-8176-8092-3_6, MR   2759046 . See also Soifer (2008), Problem 40.26, p. 496.
  8. 1 2 Horvat, Boris; Kratochvíl, Jan; Pisanski, Tomaž (2011), "On the Computational Complexity of Degenerate Unit Distance Representations of Graphs", Combinatorial Algorithms: 21st International Workshop, IWOCA 2010, London, UK, July 26-28, 2010, Revised Selected Papers, Lecture Notes in Computer Science, vol. 6460, pp. 274–285, arXiv: 1001.0886 , Bibcode:2011LNCS.6460..274H, doi:10.1007/978-3-642-19222-7_28, ISBN   978-3-642-19221-0, S2CID   17585590 .
  9. ↑ Haas, Ruth; Orden, David; Rote, Günter; Santos, Francisco; Servatius, Brigitte; Servatius, Herman; Souvaine, Diane; Streinu, Ileana; Whiteley, Walter (2005), "Planar minimally rigid graphs and pseudo-triangulations", Computational Geometry Theory and Applications , 31 (1–2): 31–61, arXiv: math/0307347 , doi:10.1016/j.comgeo.2004.07.003, MR   2131802 .
  10. ↑ Winkler, Peter (November 2011), "Puzzled: Distances Between Points on the Plane", Communications of the ACM , 54 (11): 120, doi:10.1145/2018396.2018422, S2CID   195633418 . Solution, issue 12, December 2011, doi : 10.1145/2043174.2043200.
This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.