Free

# 5-color theorem - Essay Example

Summary
The theorem states that for a given plane divided into adjoining regions, such that it results in a form of a map of countries, no more…

## Extract of sample "5-color theorem"

Five-Color Theorem The five color theorem, also referred to as the five color map theorem, is a mathematical theoremthat was developed from the graph theory. The theorem states that for a given plane divided into adjoining regions, such that it results in a form of a map of countries, no more than five colors are necessary to color the regions of the political map such that no two neighboring areas of the map are colored with the similar color. The five color theorem was developed as an extension to the four color theorem which was proved to have an error in its proof. To understand the five color theory it is necessary to go to the history behind the development of the color theorems. There are three of them, four-color, five-color and six-color theorem. The five color theorem was proved in 1890 showing that five colors suffice to color a map. (Jensen and Toft 61)
It all began with Francis Guthrie. He was a mathematician from British, who in 1952 discovered that he could color the states in the map of Great Britain by means of four colors without coloring of the neighboring countries with the same color. The problem hence arose if it was feasible to color any given map using four colors and it remained an area of interest for a while. The problem was; however, deciphered in 1879 when A. Kempe claimed to have found an explanation to the four color problem and went ahead to publish his solution and proof. In 1890; however, P. Heawood discovered an error in Kempers proof, which led to the demotion of the four color theorem as a credible theory. Heawood was unable to show that there was an error, which could have been colored with not less than five colors, but ultimately proved that Kempe was wrong in his argument. This led to a solution in the color problem with the five color theorem sufficing (Jensen and Toft 61).
In order to proof the five color theorem mathematically, one relates a planar graph, G to a certain map. A vertex is placed on every area in the map. Two vertices are then connected with an edge where analogous areas share a boundary in common. This problem is then translated into a graph coloring problem. One is now required to color the graph vertices so that no border has its endpoints with a similar color. This proof relies heavily on the Euler characteristic to illustrate that there, it is mandatory to have a vertex V that is shared by at most five borders. It also relies on the fact that G is a planar. This is to denote that G may be embedded in a plane without necessarily intersecting the borders. Now take out the vertex V, from the planar graph, G. The new graph attained after this will have one vertex less than the original graph G.
At this point, we can presume, by induction that this graph can be painted with just five colors. The vertex V must be linked with five other vertices because if not, it can be painted with the planar graph, G, with a paint not used by the other vertices. Look at the five vertices V1, V2, V3, V4, and V5 that were adjacent to V in cyclical order. It will be found that less than five colors in painting these vertices; therefore, the vertex V can be painted in order to render the planar graph five colored. At this point, we assume that V1, V2, V3, V4, V5 are colored with colors 1, 2, 3, 4, and 5 respectively. Now consider the sub graph G13 of the reduced G which consists of the vertices colored with colors 1 and 3 only and the points that connect both. If V1 and V3 occur in separate linked components, in G13, the coloration can be reversed to that having V1. It is then possible to give the color 1 to V hence solving the problem (Jensen and Toft 62).
If on the contrary, v1 and v3 are appearing on the same region on G13 it is possible to join them. A path is created joining the points that are colored with color one and color three. Turn to the sub graph G24 of the reduced G. This sub graph contains the points that have either color two or color four. Use arguments in the first sub graph G13 as above. It is now either realistic to reverse the coloration on a sub graph of G24 and paint V with color 2, alternatively we can join the point V2 with the vertex V4 through all the points that contain their respective colors. It is; therefore, clear that this path through G24 would cut through the path established in the sub graph G13. We can conclude that G can be colored using five colors, which is the complete opposite of the first assumption. This proves the latter, that the map can be colored using at least five colors, which essentially is the five-color theorem (Jensen and Toft 62).
Work Cited
Jensen, Tommy and Toft, Bjarne. Graph Coloring Problems. New York, NY: John Wiley & Sons, 1995. Print. Read More
Cite this document
• APA
• MLA
• CHICAGO
(“5-color theorem Essay Example | Topics and Well Written Essays - 500 words”, n.d.)
5-color theorem Essay Example | Topics and Well Written Essays - 500 words. Retrieved from https://studentshare.org/miscellaneous/1596153-5-color-theorem
(5-Color Theorem Essay Example | Topics and Well Written Essays - 500 Words)
5-Color Theorem Essay Example | Topics and Well Written Essays - 500 Words. https://studentshare.org/miscellaneous/1596153-5-color-theorem.
“5-Color Theorem Essay Example | Topics and Well Written Essays - 500 Words”, n.d. https://studentshare.org/miscellaneous/1596153-5-color-theorem.
Click to create a comment or rate a document

## CHECK THESE SAMPLES OF 5-color theorem

### Color

...? Color Color Color is a visual perception that corresponds in human to the categories referred to as blue, red, green, yellow and others. Color derives from the distribution of wavelength versus light power (spectrum of light) that interacts in the eye with light receptors’ spectral sensitivities (Farndon, 2003). Physical specifications and categories of color are associated with materials, objects, and light sources based on physical properties of color such as reflection of light, light absorption, or emission spectra. This paper seeks to discuss our perception of color. Color may be quantified and...
5 Pages(1250 words)Research Paper

### The Pythagorean Theorem

...representation A B C Consider a right angle triangle ABC with right angle at A. Angle BAC = 90 degree Then, the square drawn on BC opposite the right angle is equal to the two squares together on BA, AC. Thus, the sides of a right triangle are related by the squares drawn on them The Pythagorean Theorem is a statement about triangles containing a right angle. The Pythagorean Theorem states that: "The area of the square built upon the hypotenuse of a right triangle is equal to the sum of the areas of the squares upon the remaining sides." Illustratation by numbers A 16 9 B C Let the sides of the right angle triangle be 3, 4, and...
14 Pages(3500 words)Essay

### Theorem of Pythagoras in Mathematics

...true"4 . Among them the most notable was "In a right-angled triangle, the square on the hypotenuse equals the sum of the squares on the other two sides" 5. Fig 1.1 6 The alternative formulations of the fifth postulate of the theorem are less cumbersome and may be more acceptable than Euclid's own version, but none of them are so self-evident that they cannot be questioned. The importance of Pythagoras proposed theorem can be seen from the fact that Pythagoras' theorem is far from being obviously true, something that should be granted without more ado, it does not need any further justifications. "In fact, none of the other alternative formulations was felt to be...
12 Pages(3000 words)Math Problem

### International economics ( trade )

...model the country’s comparative advantage will be determined by the abundance and the price of factors of production. More precisely, the country will export those commodities in the production of which it uses its abundant and cheaper factor of production like labor. Assumption of H-O model It is a model of 2 *2*2 which means model composed of two countries trading with each other in 2 commodities with the help of 2 factors of production i.e. labor + capital. In case of long run, constant return to scale applies to the production. No transportation cost. No trade barriers. The taste of people and technology of the production remain constant. Main predictions of the factor proportions theorem The factor proportion...
7 Pages(1750 words)Essay

### Pythagorean Theorem

...Pythagorean Theorem (Add (Add (Add Pythagorean Theorem Introduction Evidences show that Pythagorean Theorem was popular even among ancient civilizations. This famous theorem was developed by the Greek mathematician and philosopher Pythagoras. Historical writings argue that though Babylonian mathematicians had knowledge in the theorem, they could not develop it into a mathematical framework. Unlike any other mathematical theorem, the Pythagorean...
3 Pages(750 words)Essay

### Color Blindness

...﻿Color blindness Color vision deficiency refers to a condition where the individual lacks the ability to perceive colors in the same way as other people. The condition is normally referred to as color blindness although there is no blindness involved. The inability to perceive color under lighting conditions is as a result of poor development of retinal cones sets. The retinal cones sets are responsible of perceiving color and relaying the signals to the brain to interpret the color. A patient suffering from this condition may misinterpret the brightness of a color or be completely unable to see the...
3 Pages(750 words)Research Paper

### Coase Theorem

...Coase Theorem Coase Theorem Coase theorem targets economic efficiency that is attributed to economic allocation and outcome when externalities are present. The theory stipulates that if trade is possible in the presence of an externality when transaction costs are significantly low, the end result will be an efficient outcome when initial allocation of property is not considered. The major obstacles to Coasian bargaining emerge when property rights have been defined poorly (Buchanan, 2005). This paper will discuss Coase theorem as an alternative to government regulation in terms of facilitating for the provision of goods and services. Ronald Coase stipulated that...
2 Pages(500 words)Essay

### Spectral graph theory

...by Fermat’s Little Theorem. In addition, I will also examine Nielson-Schreier’s point of view as far as the subject is concerned (Bonchev, Danail and Rouvray, 17). I will also discuss the concept’s new application to DNA arrangement and computer network security and its important application when it comes to the vertex cover graphs (Beineke, Lowell and Robin 69). There is also the use of edge color and matching in development of vertex colouring and this has well been explained in y work. Introduction Graph theory is very fast gaining merits in the field of mathematics as a result of its application in other different fields such as computer science, biochemistry, and biotechnology (Cvetković &...
15 Pages(3750 words)Research Paper

### Bayes' Theorem

...Bayesian Theorem Introduction Reverend Thomas Bayes developed Bayes’ theorem of probability. The theorem provides understanding about the how the probability of a theorem is affected by a new set of evidence. It is applied to in a variety of context to explore a relationship between theory and evidence. Contemporary, the theorem’s application is broad, ranging from mathematics to the field of science. It explains the relations between two theories and evidences. It allows the researcher to determine the relation between current beliefs with respect to previous beliefs and evidences. Simon Jackman (2009) defines Bayes’ theorem as ‘a...
15 Pages(3750 words)Essay

### Color

...Color Theory Understanding color theory and color models is very essential when discussing color with the art and editorial staff of a magazine. A good understanding enables a person explain in the best way possible to the staff what you need from them. The best color selection increases the chances of the magazine reaching its goals. Normally, color in design is very subjective. This means that, what evokes one reaction in one person may evoke a very different reaction in someone else. Experts relate this phenomenon to personal preference, or even due to cultural background. A good understanding of color theory is a...
1 Pages(250 words)Assignment