Five color theorem
The five- color theorem states that any map can be colored with five colors so that no two countries are contiguous with the same color.
The statement is made on the constraints that a common point does not count as " limit" and each country consists of a contiguous area, so no enclaves are present.
The five -color set is weaker than the four- color theorem and much easier to prove.
Historical
The phrase goes back to Percy Heawood. This discovered in 1879 published by Alfred Kempe and initially deemed to be correct proof of the four - color theorem one at that time irreparable errors and then proved in 1890 by elementary means the five -color set.
Graph Theoretical formulation
Formally, the simplest solution is described with the help of graph theory. Here, every country in the map is assigned to exactly one node. Two nodes of the graph are exactly connected by an ( undirected ) edge together when the countries adjacent. The resulting graph is planar (also called " planar " ) because it can be embedded into the plane due to its construction, without intersecting the edges.
For an ( arbitrary) graph is a node coloring with (at most) "Colors" a picture of the set of nodes in the crowd. The coloring is allowed if adjacent nodes get assigned different colors. The graph is called the k- dyeable (specifically knotenfärbbar k ) if there is an acceptable color with colors for him. The five -color set is now in graph-theoretical formulation:
Proof of the theorem
The proof proceeds by induction on the number of nodes in the planar graph.
- Induction base: A graph with a node is colorable with a color according to the conditions.
- Induction hypothesis: The rate applies to nodes.
- Inductive claim: The rate applies to nodes.
- Induction step: Based on the Euler polyhedral formula we can state that in any planar graph with at least one node on node degree less than or equal to 5, ie with less than six incident ( incoming ) edges or with less than 6 neighboring nodes. Case 1: In the graph, there is a node with node degree less than five. You turn the assumption on the graph corresponds without the node to. can be dyed valid with five colors. has a maximum of four neighboring nodes, and can be dyed with the present fifth color. The graph can be colored so valid.
- Case 2: There is no node in the graph with node degree less than 5 From Euler's polyhedron formula then, that there must be a node with node degree equal to 5 follows. The graph corresponding to no, is by the induction hypothesis with 5 colors. Case 2.1: The neighbor nodes of are colored with four different colors. Then stained with the fifth existing color and gives a valid coloring.
- Case 2.2: The neighbor nodes of are dyed in five different colors. Then we choose an arbitrary, fixed planar embedding and denote the neighbor nodes by using clockwise. Is there now a way of according that leads not only the colors of and ( by the induction hypothesis, logically, alternately ) used? Case 2.2.1, No: Then the node is recolored on the color of. All neighboring nodes of the color of will to the former color of recolored, etc. This gives again a valid coloring. The neighboring nodes of are now but only in four colors dyed ( now the same color as ) and can be dyed with the fifth color available, which is a valid graph coloring results.
- Case 2.2.2, Yes: (By changing the coloring as in the previous case, one can not achieve anything here, because change in the end only and the colors. ) Consider now the nodes and. Between these two nodes, there may be no way of alternately uses the colors of the two nodes, because this way would inevitably go through a node that is on the road and thus a different color than that of and has. This is due to the fact that circled so to speak, of this path and ( yes together yield a circle). Thus, at one and the same applied to Umfärbprinzip as in the previous case and. This has given the adjacent nodes of again only four colors and you can take the fifth existing color color a valid coloring to achieve.