Four Color Theorem
From Math Images
Four Color Theorem |
---|
Four Color Theorem
- This image shows a four coloring and graph representation of the United States.
Basic Description
Suppose we have a map in which no single territory is made up of disconnected regions. How many colors are needed to color the territories of this map, if all the territories that share a border segment must be of different colors?It turns out that only four colors are needed to color such a two-dimensional map. It has taken over a century for a correct proof of this fact to emerge, and currently known proofs are so long that they can only be checked with the aid of computers. An example of a map colored with only 4 colors is the map of The United States in this page's main image.
A More Mathematical Explanation
[[Image:Graphexample.JPG|thumb|left|200px|Example of a planar graph (top) and a non-planar graph (bot [...]
Graphs are useful to analyze map colorings because a map containing only connected territories can easily be converted into a planar graph by representing each territory with a vertex and each border segment with an edge, as in this page's main image. An edge is not drawn between two territories that share only a corner, such as between Utah and New Mexico. The four color theorem states that the vertices of any planar graph can be colored with at most four colors such that no adjacent vertices are the same color. Since maps can be represented by planar graphs, this theorem is equivalent to saying any map with only connected territories can be colored with at most four colors, such that no territories of the same color will share a border segment.
Teaching Materials
- There are currently no teaching materials for this page. Add teaching materials.
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.