Төрт түс теоремасын дәлездеуде қолданылатын Кемпе тізбегі

Mathematical device used in proof of the four colour theorem

In mathematics, a Kempe chain is a device used mainly in the study of the four colour theorem. Intuitively, it is a connected chain of vertices on a graph with alternating colours.

Kempe chains were first used by Alfred Kempe in his attempted proof of the four colour theorem. Even though his proof turned out to be incomplete, the method of Kempe chains is crucial to the success of valid modern proofs, such as the first successful one by Kenneth Appel and Wolfgang Haken. Furthermore, the method is used in the proof of the five colour theorem by Percy John Heawood, a weaker but more easily proven version of the four colour theorem. In this case, Kempe chains are used to prove the idea that no vertex of degree four has to be touching four distinct colours different from itself. First, one can create a graph with a vertex v and four vertices as neighbours. If we remove the vertex v, we can four colour the remaining vertices. We can set the colours as (in clockwise order) red, yellow, blue, and green. In this situation, there can be a Kempe chain joining the red and blue neighbours or a Kempe chain joining the green and yellow neighbours, but not both, since these two paths would necessarily intersect, and the vertex where they intersect cannot be coloured with both red or blue and with green or yellow at the same time. Supposing that the Kempe chain is connecting the green and yellow neighbours, red and blue must then necessarily not have a Kempe chain between them. So, when placing the original vertex v back into the graph, we can simply reverse the colours of the red vertex and its neighbours (including the red vertex, making it blue), which leaves vertex v with two blue neighbours, one green, and one yellow. This means v has only three distinct colours as neighbours, and that we can now colour vertex v as red. This results in a four coloured graph.

Kempe chains have been used to solve problems in colouring extension. Kempe chains can be used for register allocation.