Five-color set

A card colored with five colors.

The five-color theorem states that any map can be colored with five colors so that no two countries are adjacent to each other with the same color. The statement applies under the restrictions that a common point does not count as a “border” and that every country consists of a contiguous area, so there are no exclaves . The five-color theorem is weaker than the four-color theorem and much easier to prove.

Historical

The sentence goes back to Percy Heawood . In the proof of the four-color theorem published by Alfred Kempe in 1879 and initially considered to be correct, he discovered an error that was irreparable at the time, and then in 1890 proved the five-color theorem with elementary means.

Graph theoretical formulation

Transition from a colored map to a graph with node coloring.

In formal terms, the easiest way to describe the problem is with the help of graph theory . Exactly one node is assigned to each country on the map . Two nodes of the graph are connected by an (undirected) edge if and only if the countries border one another. The resulting graph is planar (also called “flattenable”) because its construction allows it to be embedded in the plane without the edges intersecting.

For any graph, a node coloring with (at most) “colors” is a mapping of the node set into the set . The coloring is allowed if neighboring nodes are assigned different colors. The graph is called k-colorable (more precisely k-knot colorable ) if there is a permissible coloration for it . The five-color theorem now reads in graph-theoretical formulation: ${\displaystyle k}$ ${\displaystyle \{1,2,\ldots ,k\}}$ ${\displaystyle k}$

Every planar graph is 5-colorable.

Proof of the theorem

The proof is carried out by complete induction on the number of nodes in the planar graph.

• Induction basis : A graph with a node can be colored with a color according to the assumptions.
• Induction hypothesis : The theorem applies to nodes. ${\displaystyle n-1}$
• Induction claim : The theorem applies to nodes. ${\displaystyle n}$
• Induction step : Based on Euler's polyhedron formula , it can be stated that in every planar graph at least one node with a node degree less than or equal to 5, i.e. H. exists with fewer than six incident (incoming) edges or with fewer than 6 neighboring nodes.
  • Case 1 : In the graph there is a node with a node degree less than five. Apply the assumption to the graph that corresponds without the node . can be validly colored with five colors. has a maximum of four neighboring nodes and can be colored with the fifth available color. The graph can therefore be validly colored. ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G(1)}$ ${\displaystyle G}$ ${\displaystyle v}$ ${\displaystyle G(1)}$ ${\displaystyle v}$
  • Case 2 : There is no node in the graph with a node degree less than 5. From Euler's polyhedron formula it follows that there must be a node with a node degree equal to 5. The graph which corresponds to without can be colored with 5 colors according to the induction assumption. ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle G(2)}$ ${\displaystyle G}$ ${\displaystyle w}$
    • Case 2.1 : The neighboring nodes of are only colored with four different colors. The fifth available color is then used to obtain a valid color. ${\displaystyle w}$ ${\displaystyle w}$
    • Case 2.2 : The neighboring nodes of are colored in five different colors. Then choose any fixed planar embedding of and designate the neighboring nodes of with clockwise. Is there a way from to that does not lead over and only uses the colors from and (logically alternating according to the induction hypothesis)? ${\displaystyle w}$ ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle w(1),w(2),\ldots ,w(5)}$ ${\displaystyle V}$ ${\displaystyle w(1)}$ ${\displaystyle w(3)}$ ${\displaystyle w}$ ${\displaystyle w(1)}$ ${\displaystyle w(3)}$
      • Case 2.2.1, No : Then the knot is recolored to the color of . All neighboring nodes of with the color of are recolored to the former color of , etc. A valid color of is obtained again . The neighboring nodes of are now only colored in four colors (they are now the same color as ) and can be colored with the fifth available color, which results in a valid graph coloring . ${\displaystyle w(1)}$ ${\displaystyle w(3)}$ ${\displaystyle w(1)}$ ${\displaystyle w(3)}$ ${\displaystyle w(1)}$ ${\displaystyle G}$ ${\displaystyle w}$ ${\displaystyle w(1)}$ ${\displaystyle w(3)}$ ${\displaystyle w}$
      • Case 2.2.2, Yes : (By changing the color as in the previous case, nothing can be achieved here, since in the end only and change the colors.) Now consider the nodes and . There can be no path between these two nodes that uses the colors of the two nodes alternately, because this path would inevitably have to go over a node that lies on the path and is therefore a different color from that of and . This is due to the fact that, so to speak, this path and (which together make up a circle) are circled. Thus the same recoloring principle can be applied to and as in the previous case to and . This means that the neighboring nodes have only four colors again and you can use the fifth available color to obtain a valid color. ${\displaystyle w(1)}$ ${\displaystyle w(3)}$ ${\displaystyle w(2)}$ ${\displaystyle w(4)}$ ${\displaystyle V}$ ${\displaystyle w(2)}$ ${\displaystyle w(4)}$ ${\displaystyle w(2)}$ ${\displaystyle V}$ ${\displaystyle w}$ ${\displaystyle w(2)}$ ${\displaystyle w(4)}$ ${\displaystyle w(1)}$ ${\displaystyle w(3)}$ ${\displaystyle w}$ ${\displaystyle w}$

algorithm

The proof directly provides an algorithm for determining a five-coloration of a planar graph in (however, there are also linear time algorithms for determining a five-coloration). ${\displaystyle G=(V,E)}$ ${\displaystyle O((|E|+|V|)\cdot |V|)}$

• def 5color (Graph G):
  • Abort case: If the graph only contains 5 nodes, color them in the 5 available colors.
  • Look for nodes with degree <5. Do you find one of these:
    • Remove the knot from G.
    • Set coloring: = 5color (G).
    • Put the node back in G and determine its coloring (this is one of the remaining colors when you list all the colors of its neighboring nodes)
    • In coloring, paste the tuple (node, color) for the freshly colored node and return coloring.
  • Look for a degree 5 node. Name it and: ${\displaystyle k}$
    • Remove from G. ${\displaystyle k}$
    • Set coloring: = 5color (G)
    • Color the graph G according to the coloring.
    • Write the adjacent nodes clockwise in a list (where we consider any planar embedding). ${\displaystyle k}$ ${\displaystyle L}$
    • Run a DFS from the first node of the list, the DFS being modified so that it only goes over nodes whose color matches one of the colors of the first / third node of the list.
    • If the DFS does not reach the third node on the list:
      • Recolor all nodes the DFS has reached (if they were previously the color of the first node in the list, recolor them the color of the third node in the list and vice versa).
      • Insert the node into graph G. ${\displaystyle k}$
      • Determine its color (one color is now free).
      • Paste the coloring of node k into coloring and print coloring.
    • If the DFS reaches the third node on the list:
      • Run a DFS from the second node of the list, the DFS being modified so that it only goes over nodes whose color matches one of the colors of the second / fourth node of the list.
      • Recolor all nodes that the DFS has reached (if they were previously the color of the second node in the list, recolor them the color of the fourth node in the list and vice versa).
      • Insert the node into graph G. ${\displaystyle k}$
      • Determine its color (one color is now free).
      • Paste the coloring of node k into coloring and print coloring.

literature

• P. J Heawood: Map-Color Theorems . In: Quarterly Journal of Mathematics , Oxford, 24, pp. 332–338
• Martin Aigner, Günter M. Ziegler: The BOOK of evidence . Springer, 4th edition, 2014, ISBN 9783662444573 , pp. 293-296

Web links

• Matroids Math Planet Detailed proof with graphics
• Sabrina Klöpfel: Sabrina Klöpfel - 5 Color Set - Elaboration.pdf The five color set . Seminar preparation, University of Marburg