Errera graph

Errera graph
	The Errera graph
Named after	Alfred Errera
Vertices	17
Edges	45
Radius	3
Diameter	4
Girth	3
Automorphisms	20 (D 10)
Chromatic number	4
Chromatic index	6
Properties	Planar ; Hamiltonian
	Table of graphs and parameters

Last updated March 30, 2019

In the mathematical field of graph theory, the Errera graph is a graph with 17 vertices and 45 edges. Alfred Errera published it in 1921 as a counterexample to Kempe's erroneous proof of the four color theorem;^[1]^[2] it was named after Errera by Hutchinson & Wagon (1998).^[1]

Mathematics Field of study concerning quantity, patterns and change

Mathematics includes the study of such topics as quantity, structure, space, and change.

Graph theory study of graphs, which are mathematical structures used to model pairwise relations between objects

In mathematics, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of vertices which are connected by edges. A distinction is made between undirected graphs, where edges link two vertices symmetrically, and directed graphs, where edges, then called arrows, link two vertices asymmetrically; see Graph for more detailed definitions and for other variations in the types of graph that are commonly considered. Graphs are one of the prime objects of study in discrete mathematics.

Vertex (graph theory) fundamental unit of which graphs (in graph theory) are formed

In mathematics, and more specifically in graph theory, a vertex or node is the fundamental unit of which graphs are formed: an undirected graph consists of a set of vertices and a set of edges, while a directed graph consists of a set of vertices and a set of arcs. In a diagram of a graph, a vertex is usually represented by a circle with a label, and an edge is represented by a line or arrow extending from one vertex to another.

Properties

The Errera graph is planar and has chromatic number 4, chromatic index 6, radius 3, diameter 4 and girth 3. All its vertices are of degree 5 or 6 and it is a 5-vertex-connected graph and a 5-edge-connected graph.

In graph theory, a planar graph is a graph that can be embedded in the plane, i.e., it can be drawn on the plane in such a way that its edges intersect only at their endpoints. In other words, it can be drawn in such a way that no edges cross each other. Such a drawing is called a plane graph or planar embedding of the graph. A plane graph can be defined as a planar graph with a mapping from every node to a point on a plane, and from every edge to a plane curve on that plane, such that the extreme points of each curve are the points mapped from its end nodes, and all curves are disjoint except on their extreme points.

In graph theory, the girth of a graph is the length of a shortest cycle contained in the graph. If the graph does not contain any cycles, its girth is defined to be infinity. For example, a 4-cycle (square) has girth 4. A grid has girth 4 as well, and a triangular mesh has girth 3. A graph with girth four or more is triangle-free.

In graph theory, a connected graph G is said to be k-vertex-connected if it has more than k vertices and remains connected whenever fewer than k vertices are removed.

The Errera graph is not a vertex-transitive graph and its full automorphism group is isomorphic to the dihedral group of order 20, the group of symmetries of a decagon, including both rotations and reflections.

In the mathematical field of graph theory, a vertex-transitive graph is a graph G such that, given any two vertices v₁ and v₂ of G, there is some automorphism

In mathematics, a dihedral group is the group of symmetries of a regular polygon, which includes rotations and reflections. Dihedral groups are among the simplest examples of finite groups, and they play an important role in group theory, geometry, and chemistry.

In geometry, a decagon is a ten-sided polygon or 10-gon.

The characteristic polynomial of the Errera graph is $-(x^{2}-2x-5)(x^{2}+x-1)^{2}(x^{3}-4x^{2}-9x+10)(x^{4}+2x^{3}-7x^{2}-18x-9)^{2}$ .

In linear algebra, the characteristic polynomial of a square matrix is a polynomial which is invariant under matrix similarity and has the eigenvalues as roots. It has the determinant and the trace of the matrix as coefficients. The characteristic polynomial of an endomorphism of vector spaces of finite dimension is the characteristic polynomial of the matrix of the endomorphism over any base; it does not depend on the choice of a basis. The characteristic equation is the equation obtained by equating to zero the characteristic polynomial.

The chromatic number of the Errera graph is 4.

The chromatic index of the Errera graph is 6.

The Errera graph is planar.

Application to the four color theorem

The four color theorem states that the vertices of every planar graph can be colored with four colors, so that no two adjacent vertices have equal colors. An erroneous proof was published in 1879 by Alfred Kempe, but it was discovered to be erroneous by 1890. The four color theorem was not given a valid proof until 1976. Kempe's proof can be translated into an algorithm to color planar graphs, which is also erroneous. Counterexamples to his proof were found in 1890 and 1896 (the Poussin graph), and later, the Fritsch graph and Soifer graph provided two smaller counterexamples.^[3] However, until the work of Errera, these counterexamples did not show that the whole coloring algorithm fails. Rather, they assumed that all but one vertex of the graph had already been colored, and showed that Kempe's method (which purportedly would modify the coloring to extend it to the whole graphs) failed in those precolored instances. The Errera graph, on the other hand, provides a counterexample to Kempe's entire method. When this method is run on the Errera graph, starting with no vertices colored, it can fail to find a valid coloring for the whole graph.^[1] Additionally, unlike the Poussin graph, all vertices in the Errera graph have degree five or more. Therefore, on this graph, it is impossible to avoid the problematic cases of Kempe's method by choosing lower-degree vertices.

In mathematics, the four color theorem, or the four color map theorem, states that, given any separation of a plane into contiguous regions, producing a figure called a map, no more than four colors are required to color the regions of the map so that no two adjacent regions have the same color. Adjacent means that two regions share a common boundary curve segment, not merely a corner where three or more regions meet. It was the first major theorem to be proved using a computer. Initially, this proof was not accepted by all mathematicians because the computer-assisted proof was infeasible for a human to check by hand. Since then the proof has gained wide acceptance, although some doubters remain.

Sir Alfred Bray Kempe DCL FRS was a mathematician best known for his work on linkages and the four colour theorem.

In mathematics and computer science, an algorithm is an unambiguous specification of how to solve a class of problems. Algorithms can perform calculation, data processing, automated reasoning, and other tasks.

The figure shows an example of how Kempe's proof can fail for this graph. In the figure, the adjacencies between regions of this map form the Errera graph, partially four-colored with the outer region uncolored. Kempe's erroneous proof follows the idea of extending partial colorings such as this one by recoloring Kempe chains, connected subgraphs that have only two colors. Any such chain can be recolored, preserving the validity of the coloring, by swapping its two colors on all vertices of the chain. Kempe's proof has different cases depending on whether the next vertex to be colored has three, four, or five neighbors and on how those neighbors are colored. In the case shown, the vertex to be colored next is the one corresponding to the outer region of the map. This region cannot be colored directly, because it already has neighbors of all four different colors. The blue and yellow neighbors are connected by a single Kempe chain (shown by the dashed yellow lines in the image), preventing a swap from making them both blue or both yellow and freeing a color. Similarly, the blue and green neighbors are connected by another Kempe chain (the dashed green lines). In such a case, Kempe's proof would try to simultaneously swap the colors on two Kempe chains, the left red-yellow chain and the right red-green chain (dashed red lines). The blue-green chain blocks the left red-yellow chain from reaching the right side of the graph, and the blue-yellow chain blocks the right red-green chain from reaching the left, so it would seem that simultaneously swapping the colors on these two chains is a safe operation. But because the blue-yellow and blue-green chains cross each other rather than staying separated, there is a region in the middle of the figure where the red-yellow and red-green chains can meet. When these two chains meet in the middle, the simultaneous swap causes adjacent yellow and green vertices in this middle area (such as the vertices represented by the upper yellow and green regions in the figure) to both become red, producing an invalid coloring.

In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem.

Applications in chemistry

Chemical graph theory concerns the graph-theoretic structure of molecules and other clusters of atoms. Both the Errera graph itself and its dual graph are relevant in this context.

Atoms of metals such as gold can form clusters in which a central atom is surrounded by twelve more atoms, in the pattern of an icosahedron. Another, larger, type of cluster can be formed by coalescing two of these icosahedral clusters, so that the central atom of each cluster becomes one of the boundary atoms for the other cluster. The resulting cluster of 19 atoms has two interior atoms (the centers of the two icosahedra) with 17 atoms in the outer shell in the pattern of the Errera graph.^[4]

The dual graph of the Errera graph is a fullerene ^[1] with 30 vertices, designated in the chemistry literature as C₃₀(D_5h)^[5] or F₃₀(D_5h)^[6] to indicate its symmetry and distinguish it from other 30-vertex fullerenes. This shape also plays a central role in the construction of higher-dimensional fullerenes.^[6]

Related Research Articles

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

In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices of a graph such that no two adjacent vertices are of the same color; this is called a vertex coloring. Similarly, an edge coloring assigns a color to each edge so that no two adjacent edges are of the same color, and a face coloring of a planar graph assigns a color to each face or region so that no two faces that share a boundary have the same color.

In graph theory, an 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.

In graph theory, a branch of mathematics, list coloring is a type of graph coloring where each vertex can be restricted to a list of allowed colors. It was first studied in the 1970s in independent papers by Vizing and by Erdős, Rubin, and Taylor.

In the mathematical field of graph theory, a snark is a simple, connected, bridgeless cubic graph with chromatic index equal to 4. In other words, it is a graph in which every vertex has three neighbors, the connectivity is redundant so that removing no one edge would split the graph, and the edges cannot be colored by only three colors without two edges of the same color meeting at a point. In order to avoid trivial cases, snarks are often restricted to have girth at least 5.

In graph theory, the Hadwiger conjecture states that, if all proper colorings of an undirected graph G use k or more colors, then one can find k disjoint connected subgraphs of G such that each subgraph is connected by an edge to each other subgraph. Contracting the edges within each of these subgraphs so that each subgraph collapses to a single vertex produces a complete graph K_k on k vertices as a minor of G.

The five color theorem is a result from graph theory that given a plane separated into regions, such as a political map of the counties of a state, the regions may be colored using no more than five colors in such a way that no two adjacent regions receive the same color.

In graph theory, Vizing's theorem states that every simple undirected graph may be edge colored using a number of colors that is at most one larger than the maximum degree $Δ$ of the graph. At least $Δ$ colors are always necessary, so the undirected graphs may be partitioned into two classes: "class one" graphs for which $Δ$ colors suffice, and "class two" graphs for which $Δ + 1$ colors are necessary. The theorem is named for Vadim G. Vizing who published it in 1964.

In the mathematical area of graph theory, a triangle-free graph is an undirected graph in which no three vertices form a triangle of edges. Triangle-free graphs may be equivalently defined as graphs with clique number ≤ 2, graphs with girth ≥ 4, graphs with no induced 3-cycle, or locally independent graphs.

In graph theory the road coloring theorem, known until recently as the road coloring conjecture, deals with synchronized instructions. The issue involves whether by using such instructions, one can reach or locate an object or destination from any other point within a network. In the real world, this phenomenon would be as if you called a friend to ask for directions to his house, and he gave you a set of directions that worked no matter where you started from. This theorem also has implications in symbolic dynamics.

In graph theory, Brooks' theorem states a relationship between the maximum degree of a graph and its chromatic number. According to the theorem, in a connected graph in which every vertex has at most Δ neighbors, the vertices can be colored with only Δ colors, except for two cases, complete graphs and cycle graphs of odd length, which require Δ + 1 colors.

In the study of graph coloring problems in mathematics and computer science, a greedy coloring or sequential coloring is a coloring of the vertices of a graph formed by a greedy algorithm that considers the vertices of the graph in sequence and assigns each vertex its first available color. Greedy colorings can be found in linear time, but they do not in general use the minimum number of colors possible.

In graph theory, an area of mathematics, an equitable coloring is an assignment of colors to the vertices of an undirected graph, in such a way that

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.$

In graph theory, the Gallai–Hasse–Roy–Vitaver theorem is a form of duality between the colorings of the vertices of a given undirected graph and the orientations of its edges. It states that the minimum number of colors needed to properly color any graph G equals one plus the length of a longest path in an orientation of G chosen to minimize this path's length. The orientations for which the longest path has minimum length always include at least one acyclic orientation.

In graph theory, the Poussin graph is a planar graph with 15 vertices and 39 edges. It is named after Charles Jean de la Vallée-Poussin.

In graph theory, a distinguishing coloring or distinguishing labeling of a graph is an assignment of colors or labels to the vertices of the graph that destroys all of the nontrivial symmetries of the graph. The coloring does not need to be a proper coloring: adjacent vertices are allowed to be given the same color. For the colored graph, there should not exist any one-to-one mapping of the vertices to themselves that preserves both adjacency and coloring. The minimum number of colors in a distinguishing coloring is called the distinguishing number of the graph.

In the mathematical field of graph theory, the Kittell graph is a planar graph with 23 vertices and 63 edges. Its unique planar embedding has 42 triangular faces. The Kittell graph is named after Irving Kittell, who used it as a counterexample to Alfred Kempe's flawed proof of the four-color theorem. Simpler counterexamples include the Errera graph and Poussin graph and the Fritsch graph and Soifer graph.

References

1 2 3 4 Hutchinson, Joan; Wagon, Stan (1998), "Kempe revisited", American Mathematical Monthly , 105 (2): 170–174, doi:10.2307/2589650, MR 1605875 .
↑ Errera, A. (1921), Du coloriage des cartes et de quelques questions d'analysis situs, Ph.D. thesis.
↑ Gethner, Ellen; Springer, William M., II (2003), "How false is Kempe's proof of the four color theorem?", Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 164: 159–175, MR 2050581 .
↑ Michael, D.; Mingos, P. (2015), "Structural and bonding patterns in gold clusters", Dalton Trans., 44 (15): 6680–6695, doi:10.1039/c5dt00253b .
↑ Mathur, Rakesh Behari; Singh, Bhanu Pratap; Pande, Shailaja (2016), Carbon Nanomaterials: Synthesis, Structure, Properties and Applications, CRC Press, p. 59, ISBN 9781498702119 .
1 2 Deza, Michel; Shtogrin, Mikhail (1999), "Three-, four-, and five-dimensional fullerenes", Southeast Asian Bulletin of Mathematics, 23 (1): 9–18, arXiv: math/9906035 , Bibcode:1999math......6035D, MR 1810781 .

External links

Weisstein, Eric W. "Errera graph". MathWorld .

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.

[hw-1] 1 2 3 4 Hutchinson, Joan; Wagon, Stan (1998), "Kempe revisited", American Mathematical Monthly , 105 (2): 170–174, doi:10.2307/2589650, MR 1605875 .

[errera-2] Errera, A. (1921), Du coloriage des cartes et de quelques questions d'analysis situs, Ph.D. thesis.

[gs-3] Gethner, Ellen; Springer, William M., II (2003), "How false is Kempe's proof of the four color theorem?", Proceedings of the Thirty-Fourth Southeastern International Conference on Combinatorics, Graph Theory and Computing, Congressus Numerantium, 164: 159–175, MR 2050581 .

[mm-4] Michael, D.; Mingos, P. (2015), "Structural and bonding patterns in gold clusters", Dalton Trans., 44 (15): 6680–6695, doi:10.1039/c5dt00253b .

[msp-5] Mathur, Rakesh Behari; Singh, Bhanu Pratap; Pande, Shailaja (2016), Carbon Nanomaterials: Synthesis, Structure, Properties and Applications, CRC Press, p. 59, ISBN 9781498702119 .

[ds-6] 1 2 Deza, Michel; Shtogrin, Mikhail (1999), "Three-, four-, and five-dimensional fullerenes", Southeast Asian Bulletin of Mathematics, 23 (1): 9–18, arXiv: math/9906035 , Bibcode:1999math......6035D, MR 1810781 .