StudentShare
Contact Us
Sign In / Sign Up for FREE
Search
Go to advanced search...
Free

Five-Color Theorem - Essay Example

Cite this document
Summary
The paper "Five-Color Theorem" tells that the five-color theorem was developed as an extension of the four-color theorem. To understand the five-color theory it is necessary to go to the history behind its development. There are three of them, four-color, five-color, and six-color theorem. …
Download full paper File format: .doc, available for editing
GRAB THE BEST PAPER92.9% of users find it useful
Five-Color Theorem
Read Text Preview

Extract of sample "Five-Color Theorem"

It all began with Francis Guthrie. He was a mathematician from British, in 1952 discovered that he could color the states in the map of Great Britain using four colors without coloring 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 for the four-color problem and went ahead to publish his solution and proof. In 1890; however, P. Heawood discovered an error in Kemper's 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 to the color problem with the five-color theorem sufficing (Jensen and Toft 61).

To prove the five-color theorem mathematically, one relates a planar graph, G to a certain map. A vertex is placed on every area on 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 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 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 to render the planar graph with five coloreds. At this point, we assume that V1, V2, V3, V4, and 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 in 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 subgraph G24 of the reduced G. This subgraph contains the points that have either color two or color four.  Use arguments in the first subgraph 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).

Read More
Tags
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.
  • Cited: 1 times

CHECK THESE SAMPLES OF Five-Color Theorem

Christine Ladd-Franklin (1847-1930)

This research paper "Christine Ladd-Franklin (1847-1930)" tends to explore her background, theoretical perspectives, and remarkable contributions especially to the field of psychology.... She's was versatile for her great contribution to the field of psychology, philosophy, mathematics, and more....
6 Pages (1500 words) Research Paper

Design paragraphs

TEST ANSWERS 1.... Generally there is a related color harmony whereby the settings are made with color schemes, which utilize a single hue or similar hues.... In this case, the color orange and violet are dominant.... The color harmony is also referred to be analogous because the color schemes used makes use of adjacent hues on the color wheel....
3 Pages (750 words) Term Paper

Polya' Theory

Polya Enumeration Theory Name Institution Polya enumeration theorem (PET) is a combinatorics theorem that follows and generalizes ultimately the Burnside's lemma on the orbits numbers of a group action in a set.... The theorem first publishing was in the year 1927 by John Howard Redfield (Po?... The theorem principle can be described using variables X, Y, and G.... According to the theorem, the number of orbits of G of colored arrangements is calculated using: ....
5 Pages (1250 words) Book Report/Review

Biopsychology: Colour Vision Theories

"Biopsychology: Colour Vision Theories" paper demonstrates the colour vision theories to explain the human ability of colour vision.... Colour vision is an integral part of human lives.... The studies and research in this field are directed at mechanisms of colour perception.... ... ... ... Colour vision represents another important component of human lives making people able to live their lives to the fullest extent....
5 Pages (1250 words) Essay

How Colors Affect Our Emotional State

The paper "How Colors Affect Our Emotional State" discusses that color is a difficult optical phenomenon that attracted much interest in science.... The nature of color was discovered a not long time ago when it became clear that color is a frequency of light interpreted by special receptors.... ...
5 Pages (1250 words) Research Paper

Multiplicity of Meanings Attached to the Use of Colour in Cinema

This review "Multiplicity of Meanings Attached to the Use of Colour in Cinema" attempts to answer the question of how best the multiplicity of color can be managed in cinema to send the right meaning to the audience.... The review analyses several theories, and concepts of the use of color in cinema....
6 Pages (1500 words) Literature review

Historical Development of Graphic Design and Animation Theories

This essay presents some conceptualized graphics as a product of color while others believed, to be stemmed from perception.... This gave rise to the Color Theory and Gestalt Principles.... Similarly, motion pictures enthusiasts replicated diversions on artistic beliefs.... .... ... ... According to the report contrary to misguided public beliefs, the perceptions of visual arts vary from one individual to another....
9 Pages (2250 words) Essay

Piagets Theory on Cognitive Development

This paper "Piaget's Theory on Cognitive Development" tells that cognitive means to understand.... A biologist Jean Piaget is the father of the cognitive development theory (Bee 1997).... This he began by studying his three sons from birth to thirteen years while he was doing his autobiography.... ...
6 Pages (1500 words) Research Paper
sponsored ads
We use cookies to create the best experience for you. Keep on browsing if you are OK with that, or find out how to manage cookies.
Contact Us