Kempe chain
Encyclopedia
In mathematics
, a Kempe chain is a device used mainly in the study of the four colour theorem.
in his attempted proof of the four colour theorem. Even though his proof turned out to be incorrect, the method of Kempe chains is crucial to the successful modern proofs (Appel & Haken, Robertson et al., etc). Furthermore, the method is used in the proof of the five-colour theorem
, a weaker form of the four-colour theorem.
Suppose G is a graph
with vertex set V, and we are given a colouring function
where S is a finite set of colours, containing at least two distinct colours a and b. If v is a vertex with colour a, then the (a, b)-Kempe chain of G containing v is the maximal connected subset of V which contains v and whose vertices are all coloured either a or b.
The above definition is what Kempe worked with. Typically the set S has four elements (the four colours of the four colour theorem), and c is a proper colouring, that is, each pair of adjacent vertices in V are assigned distinct colours.
A more general definition, which is used in the modern computer-based proofs of the four colour theorem, is the following. Suppose again that G is a graph, with edge set E, and this time we have a colouring function
If e is an edge assigned colour a, then the (a, b)-Kempe chain of G containing e is the maximal connected subset of E which contains e and whose edges are all coloured either a or b.
This second definition is typically applied where S has three elements, say a, b and c, and where V is a cubic graph
, that is, every vertex has three incident edges. If such a graph is properly coloured, then each vertex must have edges of three distinct colours, and Kempe chains end up being path
s, which is simpler than in the case of the first definition.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
, a Kempe chain is a device used mainly in the study of the four colour theorem.
History
Kempe chains were first used by Alfred KempeAlfred Kempe
Sir Alfred Bray Kempe D.C.L. F.R.S. was a mathematician best known for his work on linkages and the four color theorem....
in his attempted proof of the four colour theorem. Even though his proof turned out to be incorrect, the method of Kempe chains is crucial to the successful modern proofs (Appel & Haken, Robertson et al., etc). Furthermore, the method is used in the proof of the five-colour theorem
Five color theorem
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.The five color theorem is...
, a weaker form of the four-colour theorem.
Formal definition
The term "Kempe chain" is used in two different but related ways.Suppose G is a graph
Graph (mathematics)
In mathematics, a graph is an abstract representation of a set of objects where some pairs of the objects are connected by links. The interconnected objects are represented by mathematical abstractions called vertices, and the links that connect some pairs of vertices are called edges...
with vertex set V, and we are given a colouring function
where S is a finite set of colours, containing at least two distinct colours a and b. If v is a vertex with colour a, then the (a, b)-Kempe chain of G containing v is the maximal connected subset of V which contains v and whose vertices are all coloured either a or b.
The above definition is what Kempe worked with. Typically the set S has four elements (the four colours of the four colour theorem), and c is a proper colouring, that is, each pair of adjacent vertices in V are assigned distinct colours.
A more general definition, which is used in the modern computer-based proofs of the four colour theorem, is the following. Suppose again that G is a graph, with edge set E, and this time we have a colouring function
If e is an edge assigned colour a, then the (a, b)-Kempe chain of G containing e is the maximal connected subset of E which contains e and whose edges are all coloured either a or b.
This second definition is typically applied where S has three elements, say a, b and c, and where V is a cubic graph
Cubic graph
In the mathematical field of graph theory, a cubic graph is a graph in which all vertices have degree three. In other words a cubic graph is a 3-regular graph. Cubic graphs are also called trivalent graphs....
, that is, every vertex has three incident edges. If such a graph is properly coloured, then each vertex must have edges of three distinct colours, and Kempe chains end up being path
Path (graph theory)
In graph theory, a path in a graph is a sequence of vertices such that from each of its vertices there is an edge to the next vertex in the sequence. A path may be infinite, but a finite path always has a first vertex, called its start vertex, and a last vertex, called its end vertex. Both of them...
s, which is simpler than in the case of the first definition.