page_title: Four color theorem
section_title: Exact formulation of the problem
hierarchical_section_title: Four color theorem / Exact formulation of the problem
caption_attribution_description: English: Azerbaijan map from CIA World Factbook, converted from original GIF format Türkçe: Azerbaycan'ın CIA tarafından oluşturulmuş haritası
context_page_description: The four color theorem is a theorem of mathematics. It says that in any plane surface with regions in it, the regions can be colored with no more than four colors. Two regions that have a common border must not get the same color. They are called adjacent if they share a segment of the border, not just a point.
  This was the first theorem to be proved by a computer, in a proof by exhaustion. In proof by exhaustion, the conclusion is established by dividing it into cases, and proving each one separately. There may be a lot of cases. For example, the first proof of the four color theorem was a proof by exhaustion with 1,936 cases. This proof was controversial because most of the cases were checked by a computer program, not by hand. The shortest known proof of the four color theorem today still has over 600 cases.
  Even though the problem was first presented as a problem to color political maps of countries, mapmakers are not very interested in it. According to an article by the math historian Kenneth May, “Maps utilizing only four colors are rare, and those that do usually require only three. Books on cartography and the history of map making do not mention the four-color property.”
context_section_description: Intuitively, the four color theorem can be stated as 'given any separation of a plane into contiguous regions, called a map, the regions can be colored using at most four colors so that no two regions which are adjacent have the same color'. To be able to correctly solve the problem, it is necessary to clarify some aspects: First, all points that belong to three or more countries must be ignored. Secondly, bizarre maps with regions of finite area and infinite perimeter can require more than four colors.
  For the purpose of the theorem every "country" has to be a simply connected region, or contiguous.
  In the real world, this is not true: Alaska as part of the United States, Nakhchivan as part of Azerbaijan, and Kaliningrad as part of Russia are not contiguous. Because the territory of a particular country must be the same color, four colors may not be enough. For instance, consider a simplified map, such as the one shown on the left: In this map, the two regions labeled A belong to the same country, and must be the same color. This map then requires five colors, since the two A regions together are contiguous with four other regions, each of which is contiguous with all the others. If A had only three regions, six or more colors might be needed. In this way, it is possible to make maps that need an arbitrarily high number of colors. A similar construction also applies if a single color is used for all bodies of water, as is usual on real maps.
  An easier to state version of the theorem uses graph theory. The set of regions of a map can be represented more abstractly as an undirected graph that has a vertex for each region and an edge for every pair of regions that share a boundary segment. This graph is planar: it can be drawn in the plane without crossings by placing each vertex at an arbitrarily chosen location within the region to which it corresponds, and by drawing the edges as curves that lead without crossing within each region from the vertex location to each shared boundary point of the region. Conversely any planar graph can be formed from a map in this way. In graph-theoretic terminology, the four-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices have the same color, or for short, "every planar graph is four-colorable" (Thomas 1998, p. 849; Wilson 2002).
caption: Example of a map of Azerbaijan with non-contiguous regions
exif: {}