Four Color Theorem

From Math Images

(Difference between revisions)
Jump to: navigation, search
Current revision (12:12, 17 August 2011) (edit) (undo)
m
 
(10 intermediate revisions not shown.)
Line 1: Line 1:
-
{{Image Description
+
{{Image Description Ready
|ImageName=Four Color Theorem
|ImageName=Four Color Theorem
|Image=Usagraphfinal2.PNG
|Image=Usagraphfinal2.PNG
|ImageIntro=This image shows a four coloring and graph representation of the United States.
|ImageIntro=This image shows a four coloring and graph representation of the United States.
-
|ImageDescElem= 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?
+
|ImageDescElem=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.
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.
-
|ImageDesc=[[Image:Graphexample.JPG|thumb|left|200px|Example of a planar graph (top) and a non-planar graph (bottom)]]Map coloring is an application of Graph Theory, the study of '''graphs'''. A graph is informally a collection of points, known as '''vertices''', connected by lines, known as '''edges'''. Two vertices connected by an edge are said to be '''adjacent'''. A graph is '''planar''' if it can be drawn with no edges overlapping each other, as shown in the top figure of the diagram to the left.
 
 +
[[Image:Graphexample.JPG|thumb|left|201px|Example of a planar graph (top) and a non-planar graph (bottom)]]Map coloring is an application of Graph Theory, the study of '''graphs'''. A graph is informally a collection of points, known as '''vertices''', connected by lines, known as '''edges'''. Two vertices connected by an edge are said to be '''adjacent'''. A graph is '''planar''' if it can be drawn with no edges overlapping each other, as shown in the top figure of the diagram to the left.
-
Graphs are useful for analyzing 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.
 
-
===Coloring maps on other figures===
+
Graphs are useful for analyzing map colorings because a map containing only connected territories can easily be converted into a planar graph by representing each two-dimensional territory with a vertex (a point) 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. {{-}}
-
Graph theory is further used to analyze maps which live on objects other than a flat two-dimensional surface. For example, a map which exists on the surface of a three-dimensional sphere only needs four colors, by the following argument: project the three dimensional map onto the sphere using a [[Stereographic Projection|stereographic projection]], color the two-dimensional projection using at most four colors, then color the corresponding regions of the original 3-D map with these same colors.
+
|ImageDesc====Coloring maps on other figures===
 +
Graph theory is further used to analyze maps which live on objects other than a flat two-dimensional surface. For example, a map which exists on the surface of a sphere only needs four colors, by the following argument: project the three dimensional map onto the sphere using a [[Stereographic Projection|stereographic projection]], color the two-dimensional projection using at most four colors, then color the corresponding regions of the original 3-D map with these same colors.
-
A torus on the other hand requires seven colors, since it is possible to draw a torus with seven regions in mutual contact, as shown in the below diagram.
+
A [[Torus|torus]] on the other hand requires seven colors, since it is possible to draw a torus with seven regions in mutual contact, as shown in the below diagram.
[[Image:Projection color torus.png|right|thumb|400px|Construction of a torus such that 7 regions are in mutual contact.]]
[[Image:Projection color torus.png|right|thumb|400px|Construction of a torus such that 7 regions are in mutual contact.]]
|AuthorName=Brendan John
|AuthorName=Brendan John
|Field=Graph Theory
|Field=Graph Theory
-
|InProgress=Yes
+
|References=:*History of the four color theorem: http://www.gap-system.org/~history/HistTopics/The_four_colour_theorem.html
 +
|Pre-K=No
 +
|Elementary=No
 +
|MiddleSchool=No
 +
|HighSchool=No
 +
 
 +
|InProgress=No
}}
}}

Current revision


Four Color Theorem
Field: Graph Theory
Image Created By: Brendan John

Four Color Theorem

This image shows a four coloring and graph representation of the United States.


Contents

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.

Example of a planar graph (top) and a non-planar graph (bottom)
Example of a planar graph (top) and a non-planar graph (bottom)
Map coloring is an application of Graph Theory, the study of graphs. A graph is informally a collection of points, known as vertices, connected by lines, known as edges. Two vertices connected by an edge are said to be adjacent. A graph is planar if it can be drawn with no edges overlapping each other, as shown in the top figure of the diagram to the left.


Graphs are useful for analyzing map colorings because a map containing only connected territories can easily be converted into a planar graph by representing each two-dimensional territory with a vertex (a point) 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.

A More Mathematical Explanation

Coloring maps on other figures

Graph theory is further used to analyze maps which live on objec [...]

Coloring maps on other figures

Graph theory is further used to analyze maps which live on objects other than a flat two-dimensional surface. For example, a map which exists on the surface of a sphere only needs four colors, by the following argument: project the three dimensional map onto the sphere using a stereographic projection, color the two-dimensional projection using at most four colors, then color the corresponding regions of the original 3-D map with these same colors.

A torus on the other hand requires seven colors, since it is possible to draw a torus with seven regions in mutual contact, as shown in the below diagram.

Construction of a torus such that 7 regions are in mutual contact.
Construction of a torus such that 7 regions are in mutual contact.




Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.




References





If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.






Personal tools